Submission #101849


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl

struct UnionFind{
	vector<int> data;
	UnionFind(int size):data(size,-1){}
	int Find(int n){
		return data[n]<0?n:(data[n]=Find(data[n]));
	}
	void Unite(int a,int b){
		int ra=Find(a),rb=Find(b);
		if(ra!=rb){
			if(-data[ra]<-data[rb])
				swap(ra,rb);
			data[ra]+=data[rb];
			data[rb]=ra;
		}
	}
};

int main()
{
	for(int n,m,k;cin>>n>>m>>k && n|m|k;){
		vector<int> ss(m),ds(m);
		for(int i=0;i<m;i++){
			cin>>ss[i]>>ds[i];
			ss[i]--,ds[i]--;
		}
		vector<int> rem(m);
		
		vector<vector<int>> qs(k,vector<int>(1));
		for(auto& q:qs){
			cin>>q[0];
			if(q[0]==0){ // remove
				q.resize(2);
				cin>>q[1];
				q[1]--;
				rem[q[1]]=1;
			}
			else{        // query
				q.resize(3);
				cin>>q[1]>>q[2];
				q[1]--,q[2]--;
			}
		}
		
		UnionFind uf(n);
		for(int i=0;i<m;i++)
			if(!rem[i])
				uf.Unite(ss[i],ds[i]);
		
		reverse(begin(qs),end(qs));
		
		vector<int> res;
		for(auto& q:qs){
			if(q[0]==0){ // remove
				uf.Unite(ss[q[1]],ds[q[1]]);
			}
			else{        // query
				res.push_back(uf.Find(q[1])==uf.Find(q[2]));
			}
		}
		
		reverse(begin(res),end(res));
		for(auto x:res) cout<<(x?"YES":"NO")<<endl;
	}
}

Submission Info

Submission Time
Task D - Graph Destruction
User Running
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1335 Byte
Status AC
Exec Time 544 ms
Memory 8472 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 792 KB
10 AC 31 ms 1060 KB
11 AC 71 ms 1696 KB
12 AC 173 ms 3320 KB
13 AC 315 ms 5532 KB
14 AC 465 ms 7256 KB
15 AC 505 ms 7820 KB
16 AC 544 ms 8472 KB
17 AC 171 ms 3492 KB
18 AC 159 ms 3300 KB
19 AC 202 ms 4004 KB
2 AC 21 ms 680 KB
20 AC 382 ms 5412 KB
21 AC 205 ms 4008 KB
22 AC 280 ms 5324 KB
23 AC 204 ms 4008 KB
24 AC 140 ms 2988 KB
25 AC 161 ms 3240 KB
26 AC 415 ms 7452 KB
27 AC 135 ms 2864 KB
28 AC 150 ms 3108 KB
29 AC 327 ms 6040 KB
3 AC 21 ms 804 KB
30 AC 240 ms 4600 KB
31 AC 398 ms 7284 KB
32 AC 320 ms 6044 KB
33 AC 352 ms 6436 KB
34 AC 412 ms 7596 KB
35 AC 370 ms 6940 KB
36 AC 181 ms 3620 KB
4 AC 21 ms 928 KB
5 AC 22 ms 804 KB
50 AC 398 ms 7324 KB
6 AC 22 ms 804 KB
7 AC 23 ms 796 KB
8 AC 25 ms 932 KB
9 AC 28 ms 988 KB