Submission #1440643


Source Code Expand

#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring> 
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;

#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int>
#define sz(s) s.size()
#define all(s) (s.begin(),s.end())

const int maxn=200005;
int n,k,l;
int f1[maxn],f2[maxn],ans[maxn];
map<pii,vector<int> >mp;


int Find(int f[],int x){
	return f[x]==x?x:f[x]=Find(f,f[x]);
}

void Union(int f[],int x,int y){
	x=Find(f,x);y=Find(f,y);
	if(x!=y)f[x]=y;
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k>>l;
	REP(i,n)f1[i]=f2[i]=i;
	while(k--){
		int u,v;
		cin>>u>>v;
		Union(f1,u,v);
	}
	while(l--){
		int u,v;
		cin>>u>>v;
		Union(f2,u,v);
	}
	REP(i,n)mp[mk(Find(f1,i),Find(f2,i))].push_back(i);
	for(map<pii,vector<int> >::iterator it=mp.begin();it!=mp.end();it++){
		rep(j,it->se.size())ans[it->se[j]]=it->se.size();
	}
	REP(i,n)cout<<ans[i]<<" ";
	return 0;
}

Submission Info

Submission Time
Task D - Connectivity
User vjudge1
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1662 Byte
Status AC
Exec Time 116 ms
Memory 23040 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 18
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask1_0.txt AC 29 ms 384 KB
subtask1_1.txt AC 116 ms 23040 KB
subtask1_10.txt AC 31 ms 384 KB
subtask1_11.txt AC 104 ms 20480 KB
subtask1_12.txt AC 94 ms 19328 KB
subtask1_13.txt AC 95 ms 21376 KB
subtask1_14.txt AC 86 ms 14848 KB
subtask1_2.txt AC 79 ms 14720 KB
subtask1_3.txt AC 102 ms 21248 KB
subtask1_4.txt AC 90 ms 16256 KB
subtask1_5.txt AC 32 ms 384 KB
subtask1_6.txt AC 97 ms 19200 KB
subtask1_7.txt AC 99 ms 21376 KB
subtask1_8.txt AC 100 ms 21504 KB
subtask1_9.txt AC 75 ms 10624 KB