Submission #5119798


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
private:
	vector<long long> par;
public:
	UnionFind(int N) { par = vector<long long>(N, -1LL); }
	int find(int x);
	long long size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};
//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

long long UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	//既に同じ集合に属しているならば繋げない
	if (same(x,y)) return;

	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}

int main() {
	long long n,m;
	cin >> n >> m;
	long long ans[m+1];
	long long A[m],B[m];
	UnionFind uf(n);

	for (int i = 0;i < m;i++) {
		cin >> A[i] >> B[i];
	}

	ans[m] = n * (n - 1) / 2;
	for (int i = m - 1;i >= 0;i--) {
		if (!uf.same(A[i]-1,B[i]-1)) {
			ans[i] = ans[i+1] - uf.size(A[i]-1) * uf.size(B[i]-1);
		} else {
			ans[i] = ans[i+1];
		}
		uf.unite(A[i]-1,B[i]-1);
	}

	for(int i = 1;i < m + 1;i++) {
		cout << ans[i] << endl;
	}
}

Submission Info

Submission Time
Task D - Decayed Bridges
User harady
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1331 Byte
Status
Exec Time 219 ms
Memory 4480 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19, testcase_20, testcase_21, testcase_22, testcase_23
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB
testcase_01 1 ms 256 KB
testcase_02 167 ms 3328 KB
testcase_03 207 ms 4096 KB
testcase_04 211 ms 4480 KB
testcase_05 211 ms 4480 KB
testcase_06 1 ms 256 KB
testcase_07 197 ms 4096 KB
testcase_08 127 ms 2688 KB
testcase_09 1 ms 256 KB
testcase_10 214 ms 4480 KB
testcase_11 41 ms 1024 KB
testcase_12 1 ms 256 KB
testcase_13 213 ms 4480 KB
testcase_14 219 ms 4480 KB
testcase_15 176 ms 3712 KB
testcase_16 90 ms 1920 KB
testcase_17 199 ms 4096 KB
testcase_18 195 ms 2944 KB
testcase_19 194 ms 2816 KB
testcase_20 195 ms 2944 KB
testcase_21 1 ms 256 KB
testcase_22 25 ms 640 KB
testcase_23 51 ms 1152 KB