Submission #1440644
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],f3[maxn],col[maxn],sz[maxn];
bool vis[maxn];
vector<int>con[maxn];
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,sz[y]+=sz[x];
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k>>l;
REP(i,n)f1[i]=f2[i]=f3[i]=i,sz[i]=1;
while(k--){
int u,v;
cin>>u>>v;
Union(f1,u,v);
}
REP(i,n)con[Find(f1,i)].push_back(i),col[i]=Find(f1,i);
REP(i,n)sort(con[i].begin(),con[i].end());
while(l--){
int u,v;
cin>>u>>v;
Union(f2,u,v);
}
REP(i,n)sz[i]=1;
REP(i,n){
if(!vis[i]){
int k=col[i];
rep(j,con[k].size()){
int x=con[k][j];
if(vis[x])continue;
if(Find(f2,i)==Find(f2,x)){
Union(f3,i,x);
vis[x]=true;
}
}
}
}
REP(i,n)cout<<sz[Find(f3,i)]<<" ";
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Connectivity |
User |
vjudge1 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1868 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
15352 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
4 ms |
8448 KB |
subtask0_1.txt |
AC |
4 ms |
8448 KB |
subtask0_2.txt |
AC |
4 ms |
8448 KB |
subtask1_0.txt |
AC |
32 ms |
8576 KB |
subtask1_1.txt |
AC |
82 ms |
15232 KB |
subtask1_10.txt |
AC |
34 ms |
8576 KB |
subtask1_11.txt |
AC |
74 ms |
14464 KB |
subtask1_12.txt |
TLE |
2104 ms |
12536 KB |
subtask1_13.txt |
TLE |
2104 ms |
13308 KB |
subtask1_14.txt |
AC |
73 ms |
11520 KB |
subtask1_2.txt |
TLE |
2104 ms |
11388 KB |
subtask1_3.txt |
TLE |
2104 ms |
13048 KB |
subtask1_4.txt |
AC |
74 ms |
11776 KB |
subtask1_5.txt |
AC |
34 ms |
8576 KB |
subtask1_6.txt |
AC |
70 ms |
14080 KB |
subtask1_7.txt |
TLE |
2104 ms |
15352 KB |
subtask1_8.txt |
TLE |
2104 ms |
13048 KB |
subtask1_9.txt |
AC |
67 ms |
10752 KB |