Submission #8384910
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;
using ll = long long;
using ui = unsigned int;
const ll MOD = 1000000007;
const ll INF = 9223372036854775807;
//AtCoder Regular Contest 097-D
struct LLPair {
ll a = 0;
ll b = 0;
};
struct UnionFindTree {
ll num_node = 0;
vector<ll> parent;
vector<ll> count;
UnionFindTree(ll num_node) {
this->num_node = num_node;
parent.clear();
parent.resize(num_node);
count.clear();
count.resize(num_node);
for (ll i = 0; i < num_node; i++) {
parent[i] = i;
count[i] = 1;
}
}
ll FindRoot(ll node) {
vector<ll> found_node;
while (true) {
if (parent[node] == node) {
for (auto index : found_node) {
parent[index] = node;
}
break;
}
else {
found_node.push_back(node);
node = parent[node];
}
}
return node;
}
bool Unite(ll node1, ll node2) {
ll node1root = FindRoot(node1);
ll node2root = FindRoot(node2);
if (node1root == node2root) {
return false;
}
count[node1root] += count[node2root];
count[node2root] = 0;
parent[node2root] = node1root;
return true;
}
ll Count(ll node) {
return count[FindRoot(node)];
}
};
int main() {
ll N;
scanf("%lld", &N);
ll M;
scanf("%lld", &M);
vector<ll> p(N);
for (ll i = 0; i < N; i++) {
scanf("%lld", &p[i]);
}
vector<LLPair> sw(M);
for (ll i = 0; i < M; i++) {
scanf("%lld %lld", &sw[i].a, &sw[i].b);
}
UnionFindTree uf(N);
for (ll i = 0; i < M; i++) {
uf.Unite(sw[i].a - 1, sw[i].b - 1);
}
ll result = 0;
for (ll i = 0; i < N; i++) {
if (uf.FindRoot(p[i] - 1) == uf.FindRoot(i)) {
result++;
}
}
printf("%lld\n", result);
}
//AtCoder Grand Contest 019-B
/*
//TLE
int main() {
char A[202020];
scanf("%s", A);
ll len = strlen(A);
ll result = 1;
for (ll i = 0; i < len * 2ll - 1ll; i++) { //0:0������ 1:0�����ڂ�1�����ڂ̊� 2:1������
if (i % 2 == 0) {
ll index = i / 2;
ll searchMax = min(index, len - 1 - index);
//i/2�����ڂ𒆐S
ll count = 0;
for (ll j = 1; j <= searchMax; j++) {
if (A[index - j] != A[index + j]) {
count++;
}
}
result += count;
}
else {
ll index = i / 2;
ll searchMax = min(index + 1, len - 1 - index);
//i/2�����ڂ̉E�𒆐S
ll count = 0;
for (ll j = 0; j < searchMax; j++) {
if (A[index - j] != A[index + j + 1]) {
count++;
}
}
result += count;
}
}
printf("%lld\n", result);
}
*/
Submission Info
Submission Time |
|
Task |
D - Equals |
User |
shu_crim |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2802 Byte |
Status |
AC |
Exec Time |
54 ms |
Memory |
4096 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:84:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &N);
^
./Main.cpp:86:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &M);
^
./Main.cpp:89:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &p[i]);
^
./Main.cpp:93:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &sw[i].a, &sw[i].b);
^
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 |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
0_003.txt |
AC |
1 ms |
256 KB |
1_004.txt |
AC |
22 ms |
1792 KB |
1_005.txt |
AC |
35 ms |
4096 KB |
1_006.txt |
AC |
46 ms |
4096 KB |
1_007.txt |
AC |
1 ms |
256 KB |
1_008.txt |
AC |
1 ms |
256 KB |
1_009.txt |
AC |
1 ms |
256 KB |
1_010.txt |
AC |
1 ms |
256 KB |
1_011.txt |
AC |
1 ms |
256 KB |
1_012.txt |
AC |
1 ms |
256 KB |
1_013.txt |
AC |
1 ms |
256 KB |
1_014.txt |
AC |
2 ms |
384 KB |
1_015.txt |
AC |
1 ms |
256 KB |
1_016.txt |
AC |
1 ms |
256 KB |
1_017.txt |
AC |
2 ms |
256 KB |
1_018.txt |
AC |
21 ms |
1664 KB |
1_019.txt |
AC |
12 ms |
2560 KB |
1_020.txt |
AC |
11 ms |
2560 KB |
1_021.txt |
AC |
12 ms |
2560 KB |
1_022.txt |
AC |
54 ms |
4096 KB |