Language: C++



    AtCoder Regular Contest 096

    日本語
    takechu (Guest)

コンテスト時間: 2018-04-21(土) 21:00 ~ 2018-04-21(土) 22:40
AtCoderホームへ戻る

    トップ
    問題
    質問
    提出
    提出一覧
    順位表
    コードテスト
    解説

コードテスト
言語
ソースコード
1

#include <iostream>

2

#include <algorithm>

3

#include <numeric>

4

#include <vector>

5

#include <map>

6

#include <set>

7

#include <unordered_set>

8

#include <cmath>

9

using namespace std;

10

typedef long long ll;

11

​

12

int main( int argc, char* argv[] ){

13

  int N,M;

14

  cin >> N >> M;

15

  vector<int> P(N);

16

  for( int i=0; i<N; ++i ){

17

    cin >> P[i];

18

  }

19

  vector<int> X(M), Y(M);

20

  for( int i=0; i<N; ++i ){

21

    cin >> X[i] >> Y[i];

22

  }

23

  

24

  vector< set<int> > T;

25

  for( int i=0; i<M; ++i ){

26

    int x=X[i], y=Y[i];

27

    int x_idx=-1, y_idx=-2;

28

    for( int j=0; j<T.size(); ++j ){

29

      auto& t = T[j];

30

      if( t.count(x)>0 ) x_idx = j;

31

      if( t.count(y)>0 ) y_idx = j;

32

      if( x_idx == y_idx ){ continue; }

33

    }

34

    if( x_idx < 0 && y_idx < 0 ){

35

      T.push_back( set<int>({X[i],Y[i]}) );

36

    }

37

    if( x_idx >= 0 && y_idx < 0 ){

38

      T[x_idx].insert(y);

39

      continue;

40

    }

41

    if( x_idx < 0 && y_idx >= 0 ){

42

      T[y_idx].insert(x);

43

      continue;

44

    }

45

    if( x_idx >= 0 && y_idx >= 0 ){

46

      auto& t = T[x_idx];

47

      for( auto x : T[y_idx] ){

48

        t.insert(x);

49

      }

50

      auto it = T.begin();

51

      advance( it, y_idx );

52

      T.erase(it);

53

      continue;

54

    }

55

  }

56

​

57

  for( auto& v : T ){

58

    for( auto x : v ) cerr << " " << x;

59

    cerr << " : ";

60

    for( auto x : v ) cerr << " " << P[x-1];

61

    cerr << endl;

62

  }

63

​

64

  int c = 0;

65

  set<int> used;

66

  for( auto& v : T ){

67

    for( auto x : v ){

68

      used.insert(x);

69

      if( v.count(P[x-1]) ){

70

        c++;

71

      }

72

    }

73

  }

74

  for( int i=1; i<=N; ++i ){

75

    if( used.count(i) ) continue;

76

    if( P[i-1]==i+1 ) c++;

77

  }

78

  cout << c << endl;

79

  return 0;

80

}

※ 512 KiB まで
※ ソースコードは「Main.拡張子」で保存されます

標準入力
10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

※ 512 KiB まで
標準出力
8
標準エラー出力
 1 2 3 4 5 6 7 8 9 :  5 3 6 8 7 10 9 1 2
終了コード 	0
実行時間 	1 ms
メモリ 	1304 KB

    ルール 用語集 よくある質問 

    利用規約 プライバシーポリシー 個人情報保護方針 企業情報 お問い合わせ 資料請求 

Copyright 2018 ©AtCoder Inc. All rights reserved.


Compiler output:
a.cc:3:29: error: invalid digit "9" in octal constant
    3 |     AtCoder Regular Contest 096
      |                             ^~~
a.cc:343:1: error: extended character ※ is not valid in an identifier
  343 | ※ 512 KiB まで
      | ^
a.cc:344:1: error: extended character ※ is not valid in an identifier
  344 | ※ ソースコードは「Main.拡張子」で保存されます
      | ^
a.cc:344:3: error: extended character 「 is not valid in an identifier
  344 | ※ ソースコードは「Main.拡張子」で保存されます
      |   ^
a.cc:344:24: error: extended character 」 is not valid in an identifier
  344 | ※ ソースコードは「Main.拡張子」で保存されます
      |                        ^
a.cc:358:1: error: extended character ※ is not valid in an identifier
  358 | ※ 512 KiB まで
      | ^
a.cc:371:16: error: extended character © is not valid in an identifier
  371 | Copyright 2018 ©AtCoder Inc. All rights reserved.
      |                ^
a.cc:3:5: error: 'AtCoder' does not name a type
    3 |     AtCoder Regular Contest 096
      |     ^~~~~~~
In file included from /usr/include/c++/14/iosfwd:42,
                 from /usr/include/c++/14/ios:40,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:25:
/usr/include/c++/14/bits/postypes.h:68:11: error: 'ptrdiff_t' does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/14/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/14/bits/exception_ptr.h:38,
                 from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/14/cwchar:44,
                 from /usr/include/c++/14/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:134:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  134 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:140:29: error: 'std::size_t' has not been declared
  140 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                             ^~~
/usr/include/c++/14/new:142:31: error: 'std::size_t' has not been declared
  142 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                               ^~~
/usr/include/c++/14/new:145:26: error: declaration of 'operator new' as non-function
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/14/new:145:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:145:52: error: expected primary-expression before 'const'
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/14/new:147:26: error: declaration of 'operator new []' as non-function
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/14/new:147:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:147:54: error: expected primary-expression before 'const'
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                      ^~~~~
/usr/include/c++/14/new:154:26: error: declaration of 'operator new' as non-function
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/14/new:154:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:154:68: error: expected primary-expression before ')' token
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                                                    ^
/usr/include/c++/14/new:155:73: error: attributes after parenthesized initializer ignored [-fpermissive]
  155 |   __attribute__((__externally_visible__, __alloc_size__ (1), __malloc__));
      |                                                                         ^
/usr/include/c++/14/new:156:26: error: declaration of 'operator new' as non-function
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                          ^~~~~~~~
/usr/include/c++/14/new:156:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:156:68: error: expected primary-expression before ',' token
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                    ^
/usr/include/c++/14/new:156:70: error: expected primary-expression before 'const'
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                      ^~~~~
/usr/include/c++/14/new:162:26: error: declaration of 'operator new []' as non-function
  162 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/14/new:162:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  162 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:162:70: error: expected primary-expression before ')' token
  162 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                                                                      ^
/usr/include/c++/14/new:163:73: error: attributes after parenthesized initializer ignored [-fpermissive]
  163 |   __attribute__((__externally_visible__, __alloc_size__ (1), __malloc__));
      |                                                                         ^
/usr/include/c++/14/new:164:26: error: declaration of 'operator new []' as non-function
  164 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                          ^~~~~~~~
/usr/include/c++/14/new:164:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  164 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:164:70: error: expected primary-expression before ',' token
  164 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |