Submission #13240614


Source Code Expand

Copy
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using graph=vector<vector<int>>;

void add_edge(graph& G,int u,int v){
	G[u].emplace_back(v);
	G[v].emplace_back(u);
}

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

// u を含む T の連結成分を求める
void dfs(int u,int p,const graph& T,vector<int>& C){
	C.emplace_back(u);
	for(int v:T[u]) if(v!=p) {
		dfs(v,u,T,C);
	}
}

int get_ID(){
	static int id=0;
	return id++;
}

int main(){
	int n,q; scanf("%d%d",&n,&q);

	graph T(n);
	set<pair<int,int>> E;
	union_find U(n);
	vector<int> id(n,-1);
	rep(i,q){
		int type,u,v; scanf("%d%d%d",&type,&u,&v); u--; v--;
		if(type==1){
			if(u>v) swap(u,v);
			E.emplace(u,v);

			u=U.find(u);
			v=U.find(v);
			if(u==v) continue;

			int ch=(U.size(u)<=U.size(v)?u:v);
			if(id[ch]!=-1){
				vector<int> C;
				dfs(ch,-1,T,C);
				for(int w:C) if(w!=ch) id[w]=id[ch];
			}

			add_edge(T,u,v);
			U.unite(u,v);
		}
		else if(type==2){
			u=U.find(u);
			id[u]=get_ID();
		}
		else{
			if(u>v) swap(u,v);
			if(E.count({u,v})>0){
				puts("Yes");
				continue;
			}

			if(id[u]!=-1 && id[u]==id[v]){
				puts("Yes");
				continue;
			}

			u=U.find(u);
			v=U.find(v);
			if(id[u]!=-1 && id[u]==id[v]){
				puts("Yes");
			}
			else{
				puts("No");
			}
		}
	}

	return 0;
}

Submission Info

Submission Time
Task D - Propagating Edges
User fura2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1661 Byte
Status
Exec Time 114 ms
Memory 10616 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int n,q; scanf("%d%d",&n,&q);
                              ^
./Main.cpp:53:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int type,u,v; scanf("%d%d%d",&type,&u,&v); u--; v--;
                                            ^

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2
All 0 / 800 bigrand_0, bigrand_1, bigrand_2, bigrand_3, bigrand_4, comp_0, comp_1, comp_2, comp_3, example_0, example_1, example_2, rand_0, rand_1, rand_10, rand_11, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, randcomp_0, randcomp_1, randcomp_2, randcomp_3, randcomp_4, tenc_0, tenc_1, tenc_2, tenc_3, tree_0, tree_1, tree_2, tree_3
Case Name Status Exec Time Memory
bigrand_0 114 ms 8960 KB
bigrand_1 111 ms 8832 KB
bigrand_2 113 ms 8960 KB
bigrand_3 106 ms 8704 KB
bigrand_4 112 ms 8704 KB
comp_0 86 ms 6400 KB
comp_1 83 ms 6016 KB
comp_2 85 ms 6400 KB
comp_3 83 ms 6016 KB
example_0 1 ms 256 KB
example_1 1 ms 256 KB
example_2 1 ms 256 KB
rand_0 1 ms 256 KB
rand_1 1 ms 256 KB
rand_10 1 ms 256 KB
rand_11 1 ms 256 KB
rand_2 1 ms 256 KB
rand_3 1 ms 256 KB
rand_4 1 ms 256 KB
rand_5 1 ms 256 KB
rand_6 1 ms 256 KB
rand_7 1 ms 256 KB
rand_8 1 ms 256 KB
rand_9 1 ms 256 KB
randcomp_0 109 ms 10104 KB
randcomp_1 111 ms 10616 KB
randcomp_2 107 ms 10104 KB
randcomp_3 112 ms 10488 KB
randcomp_4 110 ms 10104 KB
tenc_0 85 ms 6272 KB
tenc_1 83 ms 5888 KB
tenc_2 86 ms 6272 KB
tenc_3 84 ms 5888 KB
tree_0 91 ms 6528 KB
tree_1 87 ms 6272 KB
tree_2 92 ms 6400 KB
tree_3 85 ms 6144 KB