Submission #394397


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<n;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
Task D - Graph Destruction
User leafmoon
Language C++ (G++ 4.6.4)
Score 0
Code Size 1372 Byte
Status WA
Exec Time 371 ms
Memory 5972 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 0 / 100
Status
AC × 2
WA × 13
RE × 22
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 50 ms 976 KB
10 RE 279 ms 1232 KB
11 WA 32 ms 1536 KB
12 WA 48 ms 2072 KB
13 RE 324 ms 2972 KB
14 WA 115 ms 3732 KB
15 WA 137 ms 4884 KB
16 WA 157 ms 5972 KB
17 RE 304 ms 2204 KB
18 RE 300 ms 2328 KB
19 RE 313 ms 2456 KB
2 RE 277 ms 1044 KB
20 RE 339 ms 3172 KB
21 RE 310 ms 2456 KB
22 WA 79 ms 3100 KB
23 WA 59 ms 2452 KB
24 WA 104 ms 2000 KB
25 RE 309 ms 2204 KB
26 RE 371 ms 4444 KB
27 WA 47 ms 1944 KB
28 WA 49 ms 2076 KB
29 RE 338 ms 3400 KB
3 AC 26 ms 932 KB
30 RE 348 ms 2840 KB
31 RE 358 ms 4056 KB
32 RE 343 ms 3352 KB
33 RE 357 ms 3612 KB
34 RE 362 ms 4440 KB
35 WA 102 ms 3668 KB
36 RE 304 ms 2332 KB
4 RE 275 ms 1184 KB
5 RE 278 ms 1224 KB
50 RE 357 ms 4124 KB
6 WA 28 ms 924 KB
7 RE 300 ms 1176 KB
8 RE 276 ms 1184 KB
9 WA 29 ms 1048 KB