#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 1e5+10;
int N,M;
ll ans = 0;
int dsu[mxn],sz[mxn];
set<pii> in[mxn],out[mxn];
map<pii,int> toaru;
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void init(){
for(int i = 1;i<=N;i++){
dsu[i] = i;
sz[i] = 1;
}
ans = 0;
return;
}
void add_edge(int a,int b){
int ra = root(a),rb = root(b);
out[ra].insert({rb,b});
in[rb].insert({ra,a});
toaru[pii(ra,rb)]++;
ans += sz[rb];
return;
}
vector<pii> v;
void combine(){
auto [a,b] = v.back();
v.pop_back();
//cerr<<"COMBINE:"<<a<<','<<b<<endl;
int ra = root(a),rb = root(b);
if(ra == rb)return;
toaru.erase(pii(rb,ra));
if(in[ra].size()+out[ra].size()>in[rb].size()+out[rb].size())swap(ra,rb);
//cerr<<"ans:"<<ans<<endl;
ans = ans-1ll*sz[ra]*in[ra].size()-1ll*sz[rb]*in[rb].size();
//cerr<<"ans:"<<ans<<endl;
while(!in[ra].empty()){
auto [rt,now] = *in[ra].begin();
in[ra].erase(in[ra].begin());
//assert(rt != ra);
if(rt == rb){
continue;
}
auto src = out[rt].lower_bound({ra,-1})->sc;
out[rt].erase(out[rt].find(pii(ra,src)));
out[rt].insert({rb,src});
toaru[pii(rt,rb)]++;
toaru[pii(rt,ra)]--;
in[rb].insert({rt,now});
auto it = in[rt].lower_bound({rb,-1});
if(it != in[rt].end()&&it->fs == rb)v.emplace_back(rb,rt);
}
while(!out[ra].empty()){
auto [rt,now] = *out[ra].begin();
out[ra].erase(out[ra].begin());
//assert(rt != ra);
if(rt == rb){
continue;
}
auto src = in[rt].lower_bound({ra,-1})->sc;
in[rt].erase(in[rt].find(pii(ra,src)));
in[rt].insert({rb,src});
toaru[pii(ra,rt)]--;
toaru[pii(rb,rt)]++;
out[rb].insert({rt,now});
auto it = out[rt].lower_bound({rb,-1});
if(it != out[rt].end()&&it->fs == rb)v.emplace_back(rb,rt);
}
out[rb].erase(out[rb].lower_bound({ra,-1}),out[rb].lower_bound({ra+1,-1}));
in[rb].erase(in[rb].lower_bound({ra,-1}),in[rb].lower_bound({ra+1,-1}));
//cerr<<a<<' '<<b<<":"<<ra<<' '<<rb<<endl;
//cerr<<"in[rb]:";for(auto &i:in[rb])cerr<<i.fs<<','<<i.sc<<' ';cerr<<endl;
//cerr<<"out[rb]:";for(auto &i:out[rb])cerr<<i.fs<<','<<i.sc<<' ';cerr<<endl;
ans += 1ll*(sz[ra]+sz[rb])*in[rb].size();
//cerr<<"ans:"<<ans<<endl;
ans += 2ll*sz[ra]*sz[rb];
dsu[ra] = rb;
sz[rb] += sz[ra];
return;
}
inline void calc(int a,int b){
int rb = root(b),ra = root(a);
if(in[rb].find(pii(ra,a)) != in[rb].end())return;
else if(ra == rb)return;
if(!toaru[pii(rb,ra)])add_edge(a,b);
else v.push_back({a,b});
while(!v.empty())combine();
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>M;
init();
for(int i = 1;i<=M;i++){
int a,b;
cin>>a>>b;
calc(a,b);
cout<<ans<<'\n';
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void combine()':
joitter2.cpp:42:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | auto [a,b] = v.back();
| ^
joitter2.cpp:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | auto [rt,now] = *in[ra].begin();
| ^
joitter2.cpp:69:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
69 | auto [rt,now] = *out[ra].begin();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
