Submission #101809
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[100000];
int par[100000];
int find(int x)
{
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return;
par[x] = y;
}
int main()
{
int n, m, k, i;
vector <pair<int, int> > v;
vector <pair<int, pair<int, int> > > w;
vector <int> z;
scanf("%d %d %d", &n, &m, &k);
for (i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--;
y--;
v.push_back(make_pair(x, y));
}
for (i = 0; i < n; i++) par[i] = i;
for (i = 0; i < k; i++) {
int x, y, z;
scanf("%d", &x);
if (x == 0) {
scanf("%d", &y);
} else {
scanf("%d %d", &y, &z);
}
y--;
z--;
if (x == 0) a[y] = 1;
w.push_back(make_pair(x, make_pair(y, z)));
}
for (i = 0; i < m; i++) {
if (a[i] == 0) unite(v[i].first, v[i].second);
}
for (i = k - 1; i >= 0; i--) {
if (w[i].first == 0) {
unite(v[w[i].second.first].first, v[w[i].second.first].second);
} else {
if (find(w[i].second.first) == find(w[i].second.second)) {
z.push_back(0);
} else {
z.push_back(1);
}
}
}
reverse(z.begin(), z.end());
for (i = 0; i < z.size(); i++) {
if (z[i] == 0) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
Submission Info
Submission Time
2013-09-21 10:16:45+0900
Task
D - Graph Destruction
User
not_shiokawa
Language
C++ (GCC 4.4.7)
Score
100
Code Size
1817 Byte
Status
AC
Exec Time
115 ms
Memory
4632 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:55: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:57: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
Judge Result
Set Name
All
Score / Max Score
100 / 100
Status
Set Name
Test Cases
All
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 4, 5, 50, 6, 7, 8, 9
Case Name
Status
Exec Time
Memory
1
AC
21 ms
928 KB
10
AC
22 ms
800 KB
11
AC
28 ms
1232 KB
12
AC
41 ms
1820 KB
13
AC
62 ms
2588 KB
14
AC
80 ms
3340 KB
15
AC
97 ms
3860 KB
16
AC
115 ms
4632 KB
17
AC
45 ms
1824 KB
18
AC
45 ms
1816 KB
19
AC
53 ms
1944 KB
2
AC
21 ms
800 KB
20
AC
69 ms
2828 KB
21
AC
51 ms
1948 KB
22
AC
66 ms
2836 KB
23
AC
52 ms
1944 KB
24
AC
40 ms
1560 KB
25
AC
43 ms
1892 KB
26
AC
93 ms
3356 KB
27
AC
42 ms
1504 KB
28
AC
43 ms
1828 KB
29
AC
72 ms
2832 KB
3
AC
21 ms
740 KB
30
AC
60 ms
2320 KB
31
AC
88 ms
3224 KB
32
AC
75 ms
2840 KB
33
AC
86 ms
3092 KB
34
AC
91 ms
3356 KB
35
AC
83 ms
3228 KB
36
AC
48 ms
1956 KB
4
AC
21 ms
808 KB
5
AC
20 ms
796 KB
50
AC
88 ms
3232 KB
6
AC
20 ms
804 KB
7
AC
20 ms
804 KB
8
AC
21 ms
804 KB
9
AC
22 ms
800 KB