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
AC × 3
AC × 12
TLE × 6
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