Submission #10448653


Source Code Expand

Copy
void main() {
	auto ip = readAs!(int[]), N = ip[0], M = ip[1], K = ip[2];
	auto friendUF = new UnionFind!int(N);
	int[][] farr = new int[][](N, 0);
	int[][] barr = new int[][](N, 0);

	debug farr.writeln;
	foreach(i; 0..M) {
		auto ip2 = readAs!(int[]), A = ip2[0], B = ip2[1];
		friendUF.unite(A-1, B-1);
		debug writefln("%d %d", A, B);
		farr[A-1] ~= B-1;
		farr[B-1] ~= A-1;
	}
	foreach(i; 0..K) {
		auto ip3 = readAs!(int[]), C = ip3[0], D = ip3[1];
		barr[C-1] ~= D-1;
		barr[D-1] ~= C-1;
	}

	ulong[] res;
	foreach(i; 0..N) {
		auto n = farr[i].length;
		auto tmp = friendUF.size(i) - n;
		foreach(v; barr[i]) {
			if(friendUF.same(v, i)) tmp--;
		}
		res ~= (tmp - 1);
	}
	writefln("%(%d %)", res);
}

class UnionFind(T) {
	T[] arr;
	this(ulong n) {
		arr.length = n;
		arr[] = -1;
	}
	T root(T x) {
		return arr[x] < 0 ? x : root(arr[x]);
	}
	bool same(T x, T y) {
		return root(x) == root(y);
	}
	bool unite(T x, T y) {
		x = root(x);
		y = root(y);
		if(x == y) return false;
		if(arr[x] > arr[y]) swap(x, y);
		arr[x] += arr[y];
		arr[y] = x;
		return true;
	}
	T size(T a) {
		return -arr[root(a)];
	}
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Submission Info

Submission Time
Task D - Friend Suggestions
User private_yusuke
Language D (DMD64 v2.070.1)
Score 400
Code Size 2196 Byte
Status AC
Exec Time 363 ms
Memory 26620 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 1 ms 256 KB
00-sample-01 AC 1 ms 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-00 AC 1 ms 256 KB
01-handmade-01 AC 1 ms 256 KB
01-handmade-02 AC 146 ms 11644 KB
01-handmade-03 AC 116 ms 11772 KB
01-handmade-04 AC 360 ms 26620 KB
01-handmade-05 AC 342 ms 21244 KB
01-handmade-06 AC 314 ms 15740 KB
02-small-00 AC 1 ms 256 KB
02-small-01 AC 1 ms 256 KB
02-small-02 AC 1 ms 256 KB
02-small-03 AC 1 ms 256 KB
02-small-04 AC 1 ms 256 KB
02-small-05 AC 1 ms 256 KB
02-small-06 AC 1 ms 256 KB
02-small-07 AC 1 ms 256 KB
02-small-08 AC 1 ms 256 KB
02-small-09 AC 1 ms 256 KB
03-large-00 AC 272 ms 22780 KB
03-large-01 AC 294 ms 23036 KB
03-large-02 AC 255 ms 22012 KB
03-large-03 AC 243 ms 22780 KB
03-large-04 AC 232 ms 22268 KB
03-large-05 AC 236 ms 21244 KB
03-large-06 AC 308 ms 21628 KB
03-large-07 AC 285 ms 22396 KB
03-large-08 AC 310 ms 24572 KB
03-large-09 AC 363 ms 24572 KB