Submission #10436906


Source Code Expand

Copy
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
void init() {
	iostream::sync_with_stdio(false);

}

#define int ll

int union_tree[200000];
int union_find(int now) {
	if (union_tree[now] == now) return now;
	return union_tree[now] = union_find(union_tree[now]);
}
void union_merge(int a, int b) {
	a = union_find(a);
	b = union_find(b);
	union_tree[a] = b;
}

vector<int> blocks[200000];

set<int> cnter[200000];

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	REP(i, n) {
		union_tree[i] = i;
	}
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		union_merge(a, b);
		blocks[a].push_back(b);
		blocks[b].push_back(a);
	}
	REP(i, k) {
		int a, b;
		cin >> a >> b;
		a--; b--;		
		blocks[a].push_back(b);
		blocks[b].push_back(a);
	}
	REP(i, n) {
		cnter[union_find(i)].insert(i);
	}
	
	REP(i, n) {
		if (i != 0) cout << " ";
		int go = union_find(i);
		int ans = cnter[go].size() - 1;
		REP(q, blocks[i].size()) {
			ans -= cnter[go].count(blocks[i][q]);
		}
		cout << ans;
	}
	cout << endl;
}

#undef int

int main() {
	init();
	solve();
}

Submission Info

Submission Time
Task D - Friend Suggestions
User kotamanegi
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1663 Byte
Status AC
Exec Time 249 ms
Memory 27124 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 30
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 02-small-00, 02-small-01, 02-small-02, 02-small-03, 02-small-04, 02-small-05, 02-small-06, 02-small-07, 02-small-08, 02-small-09, 03-large-00, 03-large-01, 03-large-02, 03-large-03, 03-large-04, 03-large-05, 03-large-06, 03-large-07, 03-large-08, 03-large-09
Case Name Status Exec Time Memory
00-sample-00 AC 6 ms 14592 KB
00-sample-01 AC 6 ms 14592 KB
00-sample-02 AC 6 ms 14592 KB
01-handmade-00 AC 6 ms 14592 KB
01-handmade-01 AC 6 ms 14592 KB
01-handmade-02 AC 77 ms 20480 KB
01-handmade-03 AC 35 ms 20352 KB
01-handmade-04 AC 249 ms 26624 KB
01-handmade-05 AC 203 ms 27124 KB
01-handmade-06 AC 89 ms 25216 KB
02-small-00 AC 6 ms 14592 KB
02-small-01 AC 6 ms 14592 KB
02-small-02 AC 6 ms 14592 KB
02-small-03 AC 6 ms 14592 KB
02-small-04 AC 6 ms 14592 KB
02-small-05 AC 6 ms 14592 KB
02-small-06 AC 6 ms 14592 KB
02-small-07 AC 6 ms 14592 KB
02-small-08 AC 6 ms 14592 KB
02-small-09 AC 6 ms 14592 KB
03-large-00 AC 120 ms 22400 KB
03-large-01 AC 151 ms 23552 KB
03-large-02 AC 130 ms 22272 KB
03-large-03 AC 110 ms 23680 KB
03-large-04 AC 121 ms 22400 KB
03-large-05 AC 110 ms 23040 KB
03-large-06 AC 106 ms 21888 KB
03-large-07 AC 137 ms 22400 KB
03-large-08 AC 177 ms 25344 KB
03-large-09 AC 178 ms 26368 KB