Submission #394398


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<m;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 100
Code Size 1372 Byte
Status AC
Exec Time 154 ms
Memory 5664 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 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 24 ms 676 KB
10 AC 25 ms 812 KB
11 AC 31 ms 1184 KB
12 AC 47 ms 1828 KB
13 AC 80 ms 2728 KB
14 AC 111 ms 3488 KB
15 AC 133 ms 4632 KB
16 AC 154 ms 5664 KB
17 AC 50 ms 1952 KB
18 AC 47 ms 1948 KB
19 AC 58 ms 2224 KB
2 AC 24 ms 676 KB
20 AC 80 ms 2852 KB
21 AC 57 ms 2208 KB
22 AC 78 ms 2856 KB
23 AC 58 ms 2212 KB
24 AC 44 ms 1824 KB
25 AC 48 ms 1956 KB
26 AC 117 ms 3876 KB
27 AC 43 ms 1696 KB
28 AC 49 ms 1828 KB
29 AC 89 ms 3108 KB
3 AC 24 ms 804 KB
30 AC 66 ms 2592 KB
31 AC 109 ms 3620 KB
32 AC 88 ms 3108 KB
33 AC 96 ms 3356 KB
34 AC 122 ms 4004 KB
35 AC 101 ms 3492 KB
36 AC 52 ms 2080 KB
4 AC 32 ms 604 KB
5 AC 24 ms 676 KB
50 AC 109 ms 3624 KB
6 AC 23 ms 924 KB
7 AC 24 ms 804 KB
8 AC 24 ms 804 KB
9 AC 24 ms 796 KB