//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();
q.pop(), q1.pop(), q2.pop(), v = gp(v);
if(m1[a[u] * n + a[v]]) return;
ii u1 = u;
m1[a[u] * n + a[v]] = 1, u = gp(u);
if(u == v) return;
if(b == 1) ans -= s[v], z[v]--;
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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
