Submission #814022

#	Time	Username	Problem	Language	Result	Execution time	Memory
814022		boyliguanhan	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1061 ms	84372 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define int long long
int p[200100],sz[200100],ans;
set<int> ch[200100], adj[200100], radj[200100];
queue<pair<int, int>> to_merge;
void ME(int x, int y) {
	adj[x].insert(y);
	radj[y].insert(x);
	if (adj[y].count(x)) to_merge.push({x, y});
}
int allssz(int x) {
	return ch[x].size() + adj[x].size() + radj[x].size();
}
int abp(int n) {
    if(p[n]-n)
        p[n]=abp(p[n]);
    return p[n];
}
void Union(int x, int y) {
	if (x == y) return;
	if (allssz(x) < allssz(y))
        swap(x, y);
	ans += sz[y] * ch[x].size() + sz[x] * ch[y].size();
    	p[y] = x;
	sz[x] += sz[y];
    	for (int i : ch[y])
		if (ch[x].count(i))
            ans -= sz[x];
		else
            ch[x].insert(i);
	adj[x].erase(y), radj[x].erase(y);
	adj[y].erase(x), radj[y].erase(x);
	for (int i : adj[y]) {
		radj[i].erase(y);
		ME(x, i);
	}
	for (int i : radj[y]) {
		adj[i].erase(y);
		ME(i, x);
	}
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    iota(p,p+200100,0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		ch[i].insert(i);
	}
	while (m--) {
		int x, y;
		cin >> x >> y;
        y = abp(y);
		if (abp(x) != y && !ch[y].count(x)) {
			ch[y].insert(x);
			ans += sz[y];
			x = abp(x);
			ME(x, y);
			while (to_merge.size()) {
				tie(x, y) = to_merge.front();
				to_merge.pop();
				Union(abp(x), abp(y));
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83