#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define mk make_pair
#define sz size()
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, void();
#define int ll
#define pii pair <int, int>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")
const int N = 1e6 + 5;
const int MOD = 998244353, INF = 2e9, sq = 650;
vector <pii> vct;
set <int> adj[N], adj2[N];
int par[N], siz[N];
int ans;
int gr (int v)
{
if (par[v] == v)
return v;
return par[v] = gr (par[v]);
}
void merge (int v, int u)
{
if (v == u)
return;
if (siz[v] < siz[u])
swap (v, u);
ans -= siz[v] * adj2[v].sz + siz[u] * adj2[u].sz;
par[u] = v;
siz[v] += siz[u];
for (int w : adj2[u])
{
int rw = gr (w);
adj2[v].insert (w);
adj[rw].insert (v);
if (adj[v].find (rw) != adj[v].end ())
vct.pb (mk (v, rw));
}
ans += siz[v] * adj2[v].sz;
for (int w : adj[u])
{
int rw = gr (w);
adj[v].insert (w);
if (adj[rw].find (v) != adj[rw].end ())
vct.pb (mk (v, rw));
}
}
void edge (int v, int u)
{
int rv = gr (v), ru = gr (u);
if (rv == ru || adj2[ru].find (v) != adj2[ru].end ())
return;
if (adj[ru].find (v) != adj[ru].end ())
{
merge (rv, ru);
while (vct.sz)
{
int vn = vct.back ().F, un = vct.back ().S;
vct.pop_back ();
merge (vn, un);
}
return;
}
ans += siz[u];
adj[rv].insert (ru);
adj2[ru].insert (v);
}
void Solve ()
{
int n, m, v, u;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
par[i] = i;
siz[i] = 1;
}
for (int i = 0; i < m; i++)
{
cin >> v >> u;
v--, u--;
edge (v, u);
cout << ans << endl;
}
}
int32_t main ()
{
ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
int tt = 1;
// cin >> tt;
while (tt--)
Solve ();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
94224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
94224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
94224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
