oj.uz

답안 #366351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366351 2021-02-14T04:37:08 Z penguinhacker 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 4 ms 5100 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 100000;
int n, m, p[mxN], sz[mxN];
ll ans = 0;
set<pair<int, int>> seen;
set<int> s[mxN];

int find(int i) {
	return i == p[i] ? i : p[i] = find(p[i]);
}

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	ans -= (ll)sz[a] * (sz[a] - 1);
	ans -= (ll)sz[b] * (sz[b] - 1);
	ans -= (ll)s[a].size() * sz[a];
	ans -= (ll)s[b].size() * sz[b];

	// now merge them
	p[b] = a;
	sz[a] += sz[b];
	if (s[a].size() < s[b].size()) swap(s[a], s[b]);
	for (const int& i : s[b]) s[a].insert(i);
	for (auto it = s[a].begin(); it != s[a].end();) {
		if (find(*it) == a) it = s[a].erase(it);
		else ++it;
	}
	ans += (ll)sz[a] * (sz[a] - 1);
	ans += (ll)s[a].size() * sz[a];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	fill(sz, sz + n, 1);
	iota(p, p + n, 0);
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		if (seen.count({b, a})) {
			merge(a, b);
		}
		else {
			seen.emplace(a, b);
			b = find(b);
			if (!s[b].count(a)) {
				ans += sz[b];
				s[find(b)].insert(a);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -