Submission #1611115


Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

typedef long long ll;

const int MAXn = 1000 * 1000 + 13, N = 2 * 100 * 1000 + 13;

vector<int> adj1[MAXn], adj2[MAXn], news;
ll cmp1[MAXn], cmp2[MAXn], cnt1, cnt2;
bool mark1[MAXn], mark2[MAXn];
map<pair<ll, ll>, ll> ans;

void bfs1(int r){
	queue<int> q;
	q.push(r);
	mark1[r] = true;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		cmp1[v] = cnt1;
		for(int i = 0; i < adj1[v].size(); i++){
			int u = adj1[v][i];
			if(!mark1[u]){
				mark1[u] = true;
				q.push(u);
			}
		}
	}
}

void bfs2(int r){
	queue<int> q;
	q.push(r);
	mark2[r] = true;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		cmp2[v] = cnt2;
		for(int i = 0; i < adj2[v].size(); i++){
			int u = adj2[v][i];
			if(!mark2[u]){
				mark2[u] = true;
				q.push(u);
			}
		}
	}
}

int main(){
	int n, k, l;
	cin >> n >> k >> l;
	for(int i = 0; i < k; i++){
		int x, y;
		cin >> x >> y;
		x--;
		y--; 
		adj1[x].push_back(y);
		adj1[y].push_back(x);
	}
	for(int i = 0; i < l; i++){
		int x, y;
		cin >> x >> y;
		x--;
		y--; 
		adj2[x].push_back(y);
		adj2[y].push_back(x);
	}
	for(int i = 0; i < n; i++)
		cmp1[i] = cmp2[i] = -1;
	cnt1 = cnt2 = 1;
	memset(mark1, 0, sizeof mark1);
	memset(mark2, 0, sizeof mark2);
	for(int i = 0; i < n; i++)
		if(!mark1[i]){
			bfs1(i);
			cnt1++;
		}
	for(int i = 0; i < n; i++)
		if(!mark2[i]){
			bfs2(i);
			cnt2++;
		}
	for(int i = 0; i < n; i++)
		ans[make_pair(cmp1[i], cmp2[i])]++;
	for(int i = 0; i < n; i++)
		cout << ans[make_pair(cmp1[i], cmp2[i])] << " ";
	cout << endl;
	return 0;
}

	

Submission Info

Submission Time
Task D - Connectivity
User vjudge3
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1645 Byte
Status AC
Exec Time 325 ms
Memory 73252 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 18 ms 52352 KB
subtask0_1.txt AC 18 ms 52352 KB
subtask0_2.txt AC 18 ms 52352 KB
subtask1_0.txt AC 106 ms 54784 KB
subtask1_1.txt AC 298 ms 70784 KB
subtask1_10.txt AC 112 ms 55040 KB
subtask1_11.txt AC 325 ms 69376 KB
subtask1_12.txt AC 229 ms 71876 KB
subtask1_13.txt AC 254 ms 72672 KB
subtask1_14.txt AC 246 ms 70912 KB
subtask1_2.txt AC 199 ms 69000 KB
subtask1_3.txt AC 253 ms 72892 KB
subtask1_4.txt AC 251 ms 71808 KB
subtask1_5.txt AC 114 ms 55040 KB
subtask1_6.txt AC 259 ms 68736 KB
subtask1_7.txt AC 242 ms 72784 KB
subtask1_8.txt AC 255 ms 73252 KB
subtask1_9.txt AC 222 ms 68096 KB