Submission #911174

#	Time	Username	Problem	Language	Result	Execution time	Memory
911174		mickey080929	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	2225 ms	113280 KiB

joitter2

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll par[100010];
ll sz[100010];
set<ll> in[100010], out[100010], all[100010];

ll Find(ll x) {
	if (x == par[x]) return x;
	return par[x] = Find(par[x]);
}

ll ans = 0;
vector<pll> mrg;

void add_edge(ll u, ll v) {
	in[v].insert(u);
	out[u].insert(v);
	if (in[u].count(v)) mrg.push_back({u, v});
}

void Union(ll x, ll y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	if (all[x].size() < all[y].size()) swap(x, y);
	ans += all[x].size() * sz[y] + all[y].size() * sz[x];
	sz[x] += sz[y];
	par[y] = x;
	for (auto &v : all[y]) {
		if (all[x].count(v)) ans -= sz[x];
		else all[x].insert(v);
	}
	in[y].erase(x); out[y].erase(x); in[x].erase(y); out[x].erase(y);
	for (auto &v : in[y]) {
		add_edge(v, x);
	}
	for (auto &v : out[y]) {
		add_edge(x, v);
	}
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	ll N, M;
	cin >> N >> M;
	for (ll i=1; i<=N; i++) {
		par[i] = i;
		sz[i] = 1;
		all[i].insert(i);
	}
	for (ll i=0; i<M; i++) {
		ll u, v;
		cin >> u >> v;
		v = Find(v);
		if (all[v].count(u)) {
			cout << ans << '\n';
			continue;
		}
		all[v].insert(u);
		ans += sz[v];
		u = Find(u);
		add_edge(u, v);
		while (!mrg.empty()) {
			auto t = mrg.back();
			mrg.pop_back();
			Union(t.first, t.second);
		}
		cout << ans << '\n';
	}
}

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