#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e9;
const ll MAXN = 1e5+100;
set <ll> s[MAXN];
set <pll> rev[MAXN];
set <ll> edge[MAXN];
ll dsu[MAXN];
ll ans;
vector <pll> all;
void join(ll x,ll y){
x = dsu[x],y = dsu[y];
if (x==y)return;
// cout<<x<<' '<<y<<'\n';
if (sz(s[x]) < sz(s[y]))swap(x,y);
for (auto it = rev[x].lower_bound(MP(y,0));it != rev[x].end() && (*it).fi == y;it=rev[x].erase(it)){
ans -= sz(s[x]);
}
for (auto it = rev[y].lower_bound(MP(x,0));it != rev[y].end() && (*it).fi == x;it=rev[y].erase(it)){
ans -= sz(s[y]);
}
ans += sz(s[x]) * sz(s[y]) * 2;
ans += sz(rev[x]) * sz(s[y]) + sz(rev[y]) * sz(s[x]);
for (auto z:rev[y]){
if (rev[x].insert(z).se == 0){
ans -= sz(s[x]) + sz(s[y]);
}
edge[z.fi].erase(y);
edge[z.fi].insert(x);
if (edge[x].find(z.fi) != edge[x].end()){
all.push_back(MP(x,z.fi));
}
}
for (auto z:edge[y]){
edge[x].insert(z);
if (z!=x){
for (auto it = rev[z].lower_bound(MP(y,0));it != rev[z].end() && (*it).fi == y;it=rev[z].erase(it)){
all.push_back(MP(x,(*it).se));
}
for (auto z1:all)rev[z].insert(z1);
}
}
edge[x].erase(y);
edge[x].erase(x);
for (auto z:s[y]){
dsu[z] = x;
s[x].insert(z);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);
ll n,m;
cin>>n>>m;
for (ll i = 1;i <= n;i ++){
s[i].insert(i);
dsu[i] = i;
}
for (ll j = 1;j <= m;j ++){
ll x,y;
cin>>x>>y;
if (dsu[x] != dsu[y]){
// x = dsu[x],y = dsu[y];
edge[dsu[x]].insert(dsu[y]);
if (rev[dsu[y]].insert(MP(dsu[x],x)).se)ans+=sz(s[dsu[y]]);
auto tmp = rev[dsu[x]].lower_bound(MP(dsu[y],0));
if (tmp != rev[dsu[x]].end() && (*tmp).fi == dsu[y]){
all.push_back(MP(dsu[x],dsu[y]));
}
// if (rev[x].find(y) != rev[x].end()){
// all.push_back(MP(x,y));
// }
while (!all.empty()){
join(all.back().fi,all.back().se);
all.pop_back();
}
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
