Submission #101820


Source Code Expand

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define mp make_pair
#define all(v) (v).begin(), (v).end()

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

struct UnionFind{
	vector<int> par, ran;
	int n;
	UnionFind(int x=0){init(x);}
	void init(int x){
		n = x;
		par.resize(x); ran.resize(x);
		fill(all(ran), 1);
		fill(all(par), -1);
	}
	int find(int x){
		if(par[x] < 0) return x;
		return par[x] = find(par[x]);
	}
	bool same(int x, int y){
		return find(x) == find(y);
	}
	bool unite(int x, int y){
		x = find(x); y = find(y);
		if(x == y) return false;
		if(ran[x] == ran[y]) ++ran[x];
		if(ran[x] < ran[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}
};

typedef pair<int, pii> Q;

int main(void){
	int n, m, k;
	cin >> n >> m >> k;
	vector<pii> edges;
	set<int> del;
	vector<Q> query;
	rep(i, m){
		int a, b;
		cin >> a >> b;
		--a; --b;
		edges.push_back(make_pair(min(a, b), max(a, b)));
	}
	rep(i, k){
		int type;
		cin >> type;
		if(type == 0){
			int e;
			cin >> e;
			--e;
			del.insert(e);
			query.push_back(mp(0, edges[e]));
		}else{
			int u, v;
			cin >> u >> v;
			--u; --v;
			query.push_back(mp(1, mp(min(u, v), max(u, v))));
		}
	}
	UnionFind uf(n);
	rep(i, m){
		if(!del.count(i)) uf.unite(edges[i].first, edges[i].second);
	}
	vector<int> res;
	for(int i = k-1; i >= 0; --i){
		if(query[i].first == 0){
			uf.unite(query[i].second.first, query[i].second.second);
		}else{
			res.push_back(uf.same(query[i].second.first, query[i].second.second));
		}
	}
	reverse(all(res));
	for(int i = 0; i < res.size(); ++i){
		if(res[i]){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}
	return 0;
}

Submission Info

Submission Time
Task D - Graph Destruction
User nikyaudo
Language C++ (G++ 4.6.4)
Score 100
Code Size 1830 Byte
Status AC
Exec Time 548 ms
Memory 5512 KB

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 736 KB
10 AC 31 ms 936 KB
11 AC 70 ms 1308 KB
12 AC 170 ms 2148 KB
13 AC 310 ms 3408 KB
14 AC 461 ms 4176 KB
15 AC 507 ms 4864 KB
16 AC 548 ms 5512 KB
17 AC 176 ms 2524 KB
18 AC 162 ms 2396 KB
19 AC 206 ms 2864 KB
2 AC 21 ms 804 KB
20 AC 292 ms 3796 KB
21 AC 202 ms 2772 KB
22 AC 285 ms 3792 KB
23 AC 206 ms 2776 KB
24 AC 140 ms 2208 KB
25 AC 160 ms 2332 KB
26 AC 425 ms 5104 KB
27 AC 135 ms 2144 KB
28 AC 150 ms 2264 KB
29 AC 332 ms 4136 KB
3 AC 21 ms 804 KB
30 AC 250 ms 3284 KB
31 AC 409 ms 4892 KB
32 AC 329 ms 4164 KB
33 AC 352 ms 4432 KB
34 AC 434 ms 5140 KB
35 AC 388 ms 4688 KB
36 AC 182 ms 2524 KB
4 AC 21 ms 928 KB
5 AC 23 ms 808 KB
50 AC 411 ms 4888 KB
6 AC 24 ms 804 KB
7 AC 23 ms 800 KB
8 AC 24 ms 928 KB
9 AC 27 ms 788 KB