Submission #635965

#	Time	Username	Problem	Language	Result	Execution time	Memory
635965		ParsaEs	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	5 ms	5076 KiB

joitter2

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "O2", "Ofast", "O3")
#pragma GCC target("sse", "sse2")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, l, r) for(ii i = l; i < r; i++)
#define pb push_back
#define X first
#define Y second
typedef long long ll;
typedef int ii;
using namespace std;
typedef pair<ii, ii> pi;
const ii xn = 1e5 + 5;
vector<pi> g[xn];
vector<ii> g1[xn];
ll s[xn], z[xn], ans;
ii p[xn], a[xn], n;
unordered_map<ii, ll> m;
unordered_map<ii, bool> m1;
queue<ii> q, q1, q2;
ii gp(ii v)
{
	return p[v] == v ? v : p[v] = gp(p[v]);
}
inline void doj()
{
	ii u = q.front(), v = q1.front(), b = q2.front();
	ii u1 = u;
	q.pop(), q1.pop(), q2.pop(), u = gp(u), v = gp(v);
	if(u == v) return;
	if(b == 1) m1[a[u1] * n + a[v]] = 0, ans -= s[v], z[v]--;
	if(m1[a[u1] * n + a[v]]) return;
	m1[a[u1] * n + a[v]] = 1;
	if(!m[a[v] * n + a[u]])
	{
		m[a[u] * n + a[v]]++, ans += s[v], z[v]++;
		if(b < 2) g[a[u]].pb({u1, v});
		if(b != 1) g1[a[v]].pb(u1);
		return;
	}
	ll c = m[a[v] * n + a[u]];
	ans -= s[u] * c, z[u] -= c;
	if(s[u] < s[v]) swap(u, v);
	if(g[a[u]].size() + g1[a[u]].size() < g[a[v]].size() + g1[a[v]].size())
		swap(a[u], a[v]), swap(s[u], s[v]), swap(z[u], z[v]);
	ans += (s[u] * 2 - z[v] + z[u]) * s[v], s[u] += s[v], p[v] = u;
	for(pi i : g[a[v]]) q.push(i.X), q1.push(i.Y), q2.push(1);
	g[a[v]].clear();
	for(ii i : g1[a[v]]) q.push(i), q1.push(u), q2.push(2);
	g1[a[v]].clear();
}
ii main()
{
	Fast;
	ii e;
	cin >> n >> e;
	rep(i, 0, n) a[i] = p[i] = i, s[i] = 1;
	while(e--)
	{
		ii u, v;
		cin >> u >> v;
		q.push(u - 1), q1.push(v - 1), q2.push(0);
		while(!q.empty()) doj();
		cout << ans << '\n';
	}
}

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