Submission #2502844
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <numeric> #include <queue> #include <map> #include <set> #include <string> #include <functional> #include <list> #include <random> #include <time.h> #define int long long #define oku7 1000000007 #define MAXN (int)1e+5 * 2+1 #define LL_MAX 9223372036854775807 //ない環境用 using namespace std; std::mt19937 mt((int)time(0)); int dx[4] = { 0, 1, 0,-1 }; // x軸方向への変位 int dy[4] = { 1, 0,-1, 0 }; // y軸方向への変位 struct uf_tree { std::vector<int> parent; int __size; uf_tree(int size_) : parent(size_, -1), __size(size_) {} void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { if (parent[y] < parent[x]) std::swap(x, y); parent[x] += parent[y]; parent[y] = x; __size--; } } bool is_same(int x, int y) { return find(x) == find(y); } int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); } int size(int x) { return -parent[find(x)]; } int size() { return __size; } }; int p[1000000]; signed main() { uf_tree uf(1000000); int N, M; cin >> N >> M; for (int i = 1; i <= N; i++) { int tmp; cin >> tmp; p[i] = tmp; } for (int i = 0; i < M; i++) { int x, y; cin >> x >> y; uf.unite(x, y); } int ans = 0; for (int i = 1; i <= N; i++) { if (uf.is_same(i, p[i])) ans++; } cout << ans << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Equals |
User | ymduu |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1500 Byte |
Status | AC |
Exec Time | 89 ms |
Memory | 8832 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 4 ms | 8064 KB |
0_001.txt | AC | 3 ms | 8064 KB |
0_002.txt | AC | 3 ms | 8064 KB |
0_003.txt | AC | 3 ms | 8064 KB |
1_004.txt | AC | 44 ms | 8064 KB |
1_005.txt | AC | 85 ms | 8832 KB |
1_006.txt | AC | 89 ms | 8832 KB |
1_007.txt | AC | 3 ms | 8064 KB |
1_008.txt | AC | 3 ms | 8064 KB |
1_009.txt | AC | 3 ms | 8064 KB |
1_010.txt | AC | 4 ms | 8064 KB |
1_011.txt | AC | 4 ms | 8064 KB |
1_012.txt | AC | 3 ms | 8064 KB |
1_013.txt | AC | 3 ms | 8064 KB |
1_014.txt | AC | 5 ms | 8064 KB |
1_015.txt | AC | 4 ms | 8064 KB |
1_016.txt | AC | 4 ms | 8064 KB |
1_017.txt | AC | 4 ms | 8064 KB |
1_018.txt | AC | 41 ms | 8064 KB |
1_019.txt | AC | 31 ms | 8832 KB |
1_020.txt | AC | 31 ms | 8832 KB |
1_021.txt | AC | 32 ms | 8832 KB |
1_022.txt | AC | 88 ms | 8832 KB |