Submission #101973


Source Code Expand

#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <map>

using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

struct Query {
	int t, a, b;
};

class UnionFindTree {

private:
	vector<int> parent;
	vector<int> rank;

public:
	explicit UnionFindTree(int n = 0) :
		parent(n), rank(n)
	{
		for(int i = 0; i < n; ++i){ parent[i] = i; }
	}
	int find(int x){
		if(parent[x] == x){ return x; }
		parent[x] = find(parent[x]);
		return parent[x];
	}
	int unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y){ return x; }
		if(rank[x] < rank[y]){
			parent[x] = y;
			return y;
		}else if(rank[x] > rank[y]){
			parent[y] = x;
			return x;
		}else{
			parent[y] = x;
			++rank[x];
			return x;
		}
	}
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(){
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	vector<pii> edges(m);
	for(int i = 0; i < m; ++i){
		int a, b;
		scanf("%d%d", &a, &b);
		edges[i] = pii(a - 1, b - 1);
	}
	const int SQRT_N = 500;
	vector<int> destructed(m);
	for(int i = 0; i < k; i += SQRT_N){
		vector<Query> queries;
		for(int j = 0; j < SQRT_N && i + j < k; ++j){
			Query q;
			scanf("%d%d", &q.t, &q.a);
			if(q.t == 0){
				--q.a;
				destructed[q.a] = 1;
			}else if(q.t == 1){
				scanf("%d", &q.b);
				--q.a; --q.b;
			}
			queries.push_back(q);
		}
		UnionFindTree uft(n);
		for(int j = 0; j < m; ++j){
			if(destructed[j]){ continue; }
			uft.unite(edges[j].first, edges[j].second);
		}
		vector<bool> appeared(n);
		for(int j = 0; j < queries.size(); ++j){
			const Query &q = queries[j];
			if(q.t == 0){ continue; }
			const int a = uft.find(q.a), b = uft.find(q.b);
			appeared[a] = appeared[b] = true;
		}
		vector< vector<int> > conn(n);
		vector<ppp> rem(queries.size());
		for(int j = 0; j < queries.size(); ++j){
			Query &q = queries[j];
			if(q.t != 0){ continue; }
			const int a = uft.find(edges[q.a].first);
			const int b = uft.find(edges[q.a].second);
			if(a == b){
				q.t == 2;
			}else if(!appeared[a] || !appeared[b]){
				q.t == 2;
			}
			rem[j].first = pii(a, conn[a].size());
			rem[j].second = pii(b, conn[b].size());
			conn[a].push_back(b);
			conn[b].push_back(a);
		}
		vector<int> passed(n, -1);
		for(int j = 0; j < queries.size(); ++j){
			const Query &q = queries[j];
			if(q.t == 0){
				const pii p0 = rem[j].first, p1 = rem[j].second;
				const int a = uft.find(p0.first);
				const int b = uft.find(p1.first);
				if(a == b){ continue; }
				conn[p0.first][p0.second] = p0.first;
				conn[p1.first][p1.second] = p1.first;
			}else{
				const int a = uft.find(q.a), b = uft.find(q.b);
				queue<int> que;
				que.push(a);
				passed[a] = j;
				bool reach = (a == b);
				while(!reach && !que.empty()){
					const int v = que.front();
					que.pop();
					for(int l = 0; l < conn[v].size(); ++l){
						const int u = conn[v][l];
						if(u == b){ reach = true; break; }
						if(passed[u] >= j){ continue; }
						passed[u] = j;
						que.push(u);
					}
				}
				puts(reach ? "YES" : "NO");
			}
		}
	}
	return 0;
}

Submission Info

Submission Time
Task D - Graph Destruction
User neteru_AA
Language C++ (G++ 4.6.4)
Score 100
Code Size 3204 Byte
Status AC
Exec Time 1172 ms
Memory 5724 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:59:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:68:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:73:22: 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
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 800 KB
10 AC 23 ms 804 KB
11 AC 32 ms 796 KB
12 AC 62 ms 996 KB
13 AC 112 ms 1188 KB
14 AC 206 ms 1880 KB
15 AC 659 ms 3872 KB
16 AC 1172 ms 5724 KB
17 AC 92 ms 1452 KB
18 AC 85 ms 1380 KB
19 AC 117 ms 1772 KB
2 AC 21 ms 736 KB
20 AC 184 ms 1872 KB
21 AC 116 ms 1736 KB
22 AC 178 ms 1816 KB
23 AC 116 ms 1512 KB
24 AC 74 ms 1392 KB
25 AC 87 ms 1524 KB
26 AC 399 ms 2292 KB
27 AC 70 ms 1316 KB
28 AC 80 ms 1332 KB
29 AC 211 ms 1796 KB
3 AC 20 ms 676 KB
30 AC 140 ms 1572 KB
31 AC 297 ms 2076 KB
32 AC 206 ms 1668 KB
33 AC 248 ms 2028 KB
34 AC 414 ms 2264 KB
35 AC 267 ms 1988 KB
36 AC 99 ms 1520 KB
4 AC 21 ms 800 KB
5 AC 21 ms 800 KB
50 AC 291 ms 1996 KB
6 AC 22 ms 800 KB
7 AC 21 ms 804 KB
8 AC 21 ms 808 KB
9 AC 22 ms 808 KB