Submission #682051

#	Time	Username	Problem	Language	Result	Execution time	Memory
682051		Kahou	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	814 ms	64716 KiB

joitter2

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 50;
int n, m, id[N];
vector<int> vc[N];
set<int> adj[2][N], st[N];
queue<pii> q;
ll ans;

void uniset(int u, int v) {
	u = id[u], v= id[v];
	if (u == v) return;

	if (vc[u].size() < vc[v].size()) swap(u, v);

	ans -= 1ll*st[u].size()*vc[u].size();
	ans -= 1ll*st[v].size()*vc[v].size();

	ans += 2ll*vc[u].size()*vc[v].size();
	
	for (int x:vc[v]) {
		id[x] = u;
		vc[u].push_back(x);
		st[u].erase(x);
	}
	vc[v].clear();
	for (int x:st[v]) {
		if (id[x] != u) {
			st[u].insert(x);
		}
	}
	st[v].clear();

	ans += 1ll*st[u].size()*vc[u].size();
	adj[0][u].erase(v);
	adj[1][u].erase(v);
	for (int x:adj[0][v]) {
		if (x == u) continue;

		adj[1][x].erase(v);
		adj[1][x].insert(u);

		if (adj[1][u].find(x) != adj[1][u].end()) q.push({u, x});
		adj[0][u].insert(x);
	}
	adj[0][v].clear();
	for (int x:adj[1][v]) {
		if (x == u) continue;

		adj[0][x].erase(v);
		adj[0][x].insert(u);

		if (adj[0][u].find(x) != adj[0][u].end()) q.push({u, x});
		adj[1][u].insert(x);
	}
	adj[1][v].clear();
}
void solve() {
	cin >> n >> m;
	for (int u = 1; u <= n; u++) {
		id[u] = u;
		vc[u].push_back(u);
	}
	while (m--) {
		int u, v;
		cin >> u >> v;

		v = id[v];
		if (id[u] != id[v] && st[v].find(u) == st[v].end()) {
			ans += vc[v].size();
			st[v].insert(u);
		}

		u = id[u];
		adj[0][u].insert(v);
		adj[1][v].insert(u);
		if (adj[0][v].find(u) != adj[0][v].end()) q.push({u, v});
		while (q.size()) {
			int x = q.front().F, y = q.front().S;
			q.pop();
			uniset(x, y);
		}
		cout << ans << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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