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 |
|
|
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 |