#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+10,mod = 998244353,inf = 1e9+10,sq = 700;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k /= 2;
}
return z;
}
int par[N],sz[N];
ll ans;
set<pll> in[N],out[N];
int getpar(int v){
if (v == par[v]) return v;
return par[v] = getpar(par[v]);
}
inline void mg(int u,int v){
if (getpar(u) == getpar(v)) return;
ans += 2ll*sz[u]*sz[v];
while (!out[v].empty()){
auto it = out[v].lower_bound({u,0});
if (it == out[v].end() || it->X != u) break;
ans -= sz[u];
out[v].erase(it);
}
while (!out[u].empty()){
auto it = out[u].lower_bound({v,0});
if (it == out[u].end() || it->X != v) break;
ans -= sz[v];
out[u].erase(it);
}
while (!in[v].empty()){
auto it = in[v].lower_bound({u,0});
if (it == in[v].end() || it->X != u) break;
in[v].erase(it);
}
while (!in[u].empty()){
auto it = in[u].lower_bound({v,0});
if (it == in[u].end() || it->X != v) break;
in[u].erase(it);
}
if (out[u].size()+in[u].size() > out[v].size()+in[v].size()) swap(u,v);
par[u] = v;
sz[v] += sz[u];
vector<int> nxt;
int beg = in[v].size(),mosh = 0;
for (pll p : out[u]){
auto it = in[v].lower_bound({p.X,0});
if (it != in[v].end() && it->X == p.X) nxt.pb(p.X);
out[v].insert(p);
in[p.X].erase({u,p.Y});
in[p.X].insert({v,p.Y});
}
for (pll p : in[u]){
out[p.X].erase({u,p.Y});
if (in[v].find(p) != in[v].end()){
mosh++;
continue;
}
auto it = out[v].lower_bound({p.X,0});
if (it != out[v].end() && it->X == p.X) nxt.pb(p.X);
out[p.X].insert({v,p.Y});
in[v].insert(p);
ans += sz[v];
}
out[u].clear();
in[u].clear();
ans += 1ll*sz[u]*(beg-mosh);
for (int w : nxt) mg(w,v);
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
int n,q;
cin >> n >> q;
rep(i,1,n+1){
par[i] = i;
sz[i] = 1;
}
while (q--){
int u,v;
cin >> u >> v;
getpar(u);
getpar(v);
if (par[u] == par[v] || out[par[u]].find({par[v],u}) != out[par[u]].end()){
cout << ans << endl;
continue;
}
out[par[u]].insert({par[v],u});
in[par[v]].insert({par[u],u});
u = getpar(u);
v = getpar(v);
ans += sz[v];
auto it = out[v].lower_bound({u,0});
if (it != out[v].end() && it->X == u){
mg(u,v);
cout << ans << endl;
}
else{
cout << ans << endl;
continue;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
