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
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
AC × 37
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