Submission #101812
Source Code Expand
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct query
{
int type;
int v, w;
};
int N, M, K;
int uf[100000];
int V[100000], W[100000];
bool use[100000];
query Q[100000];
vector<bool> ret;
int q, v, w;
int root(int p){
return (uf[p] < 0) ? p : (uf[p] = root(uf[p]));
}
void join(int p, int q)
{
p = root(p);
q = root(q);
if(p==q) return;
uf[p] += uf[q
]
;
uf[q] = p;
}
int main()
{
scanf("%d%d%d", &N, &M, &K);
for(int i=0;i<N;i++) uf[i] = -1;
for(int i=0;i<M;i++){
scanf("%d%d", &v, &w);
--v; --w;
use[i] = true;
V[i] = v; W[i] = w;
}
for(int i=0;i<K;i++){
scanf("%d", &q);
Q[i].type = q;
if(q==0){
scanf("%d", &v);
--v;
use[v] = false;
Q[i].v = v;
}else{
scanf("%d%d", &v, &w);
--v; --w;
Q[i].v = v;
Q[i].w = w;
}
}
for(int i=0;i<M;i++){
if(use[i]){
join(V[i], W[i]);
}
}
for(int i=K-1;i>=0;i--){
if(Q[i].type == 0){
int qt = Q[i].v;
join(V[qt], W[qt]);
}else{
ret.push_back(root(Q[i].v) == root(Q[i].w));
}
}
for(int i=ret.size()-1;i>=0;i--) puts(ret[i] ? "YES" : "NO");
return 0;
}
Submission Info
Submission Time
2013-09-21 10:17:56+0900
Task
D - Graph Destruction
User
Operasan
Language
C++ (GCC 4.4.7)
Score
100
Code Size
1196 Byte
Status
AC
Exec Time
110 ms
Memory
3492 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:49: 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: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
22 ms
804 KB
10
AC
22 ms
932 KB
11
AC
28 ms
1064 KB
12
AC
41 ms
1448 KB
13
AC
70 ms
1968 KB
14
AC
78 ms
2416 KB
15
AC
93 ms
2988 KB
16
AC
110 ms
3492 KB
17
AC
44 ms
1448 KB
18
AC
42 ms
1440 KB
19
AC
51 ms
1652 KB
2
AC
21 ms
808 KB
20
AC
63 ms
2084 KB
21
AC
50 ms
1632 KB
22
AC
63 ms
1956 KB
23
AC
51 ms
1696 KB
24
AC
39 ms
1312 KB
25
AC
42 ms
1444 KB
26
AC
85 ms
2716 KB
27
AC
39 ms
1320 KB
28
AC
41 ms
1436 KB
29
AC
68 ms
2212 KB
3
AC
20 ms
804 KB
30
AC
54 ms
1816 KB
31
AC
81 ms
2528 KB
32
AC
68 ms
2216 KB
33
AC
72 ms
2332 KB
34
AC
89 ms
2696 KB
35
AC
78 ms
2472 KB
36
AC
46 ms
1564 KB
4
AC
21 ms
796 KB
5
AC
22 ms
932 KB
50
AC
79 ms
2604 KB
6
AC
21 ms
932 KB
7
AC
20 ms
804 KB
8
AC
22 ms
928 KB
9
AC
20 ms
804 KB