Submission #394398
Source Code Expand
#include <vector>
#include <cstdio>
using namespace std;
typedef pair<int,long long> pil;
class union_find{
vector<int> parent;
public:
vector<int> marked;
int root(int a){return parent[a]==a||marked[a]?a:(parent[a]=root(parent[a]));}
union_find(int n):parent(n),marked(n){for(int i=1;i<n;i++)parent[i]=i;}
int same(int a,int b){return root(a)==root(b);}
int unite(int a,int b){
int x=root(a),y=root(b);//if(x==y)return 0;
parent[x]=y;
return 1;
}
};
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
union_find uf(n);
vector<pil>edge(m);
for(int i=0;i<m;i++){
scanf("%d%lld",&edge[i].first,&edge[i].second);
edge[i].first--;
edge[i].second--;
}
vector<pil>query(k);
vector<int>flag(m);
for(int i=0;i<k;i++){
int a,b,c;
scanf("%d",&a);
if(a){
scanf("%d%d",&b,&c);
b--,c--;
query[i]=make_pair(a,(long long)b<<32|c);
}else{
scanf("%d",&b);
b--;
query[i]=make_pair(a,b);
flag[b]=1;
}
}
for(int i=0;i<m;i++)if(!flag[i])uf.unite(edge[i].first,edge[i].second);
vector<int>result;
for(int i=k-1;i>=0;i--){
if(query[i].first){
int b=query[i].second>>32,c=query[i].second;
result.push_back(uf.same(b,c));
}else{
uf.unite(edge[query[i].second].first,edge[query[i].second].second);
}
}
for(int i=result.size()-1;i>=0;i--)puts(result[i]?"YES":"NO");
}
Submission Info
Submission Time
2015-04-27 17:08:57+0900
Task
D - Graph Destruction
User
leafmoon
Language
C++ (G++ 4.6.4)
Score
100
Code Size
1372 Byte
Status
AC
Exec Time
154 ms
Memory
5664 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:20:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:24:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:32:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:34:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:38:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-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
24 ms
676 KB
10
AC
25 ms
812 KB
11
AC
31 ms
1184 KB
12
AC
47 ms
1828 KB
13
AC
80 ms
2728 KB
14
AC
111 ms
3488 KB
15
AC
133 ms
4632 KB
16
AC
154 ms
5664 KB
17
AC
50 ms
1952 KB
18
AC
47 ms
1948 KB
19
AC
58 ms
2224 KB
2
AC
24 ms
676 KB
20
AC
80 ms
2852 KB
21
AC
57 ms
2208 KB
22
AC
78 ms
2856 KB
23
AC
58 ms
2212 KB
24
AC
44 ms
1824 KB
25
AC
48 ms
1956 KB
26
AC
117 ms
3876 KB
27
AC
43 ms
1696 KB
28
AC
49 ms
1828 KB
29
AC
89 ms
3108 KB
3
AC
24 ms
804 KB
30
AC
66 ms
2592 KB
31
AC
109 ms
3620 KB
32
AC
88 ms
3108 KB
33
AC
96 ms
3356 KB
34
AC
122 ms
4004 KB
35
AC
101 ms
3492 KB
36
AC
52 ms
2080 KB
4
AC
32 ms
604 KB
5
AC
24 ms
676 KB
50
AC
109 ms
3624 KB
6
AC
23 ms
924 KB
7
AC
24 ms
804 KB
8
AC
24 ms
804 KB
9
AC
24 ms
796 KB