#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const I M=300000;
pair<I,I>fols[M];
set<pair<I,I>>viss;
vector<I>mems[N];
set<I>incs[N],outs[N];
I pars[N];
Lli res=0;
I fnd(I i){
if(pars[i]<0)return i;
return pars[i]=fnd(pars[i]);
}
void uni(I a,I b){
if((a=fnd(a))==(b=fnd(b)))return;
if(pars[a]>pars[b])swap(a,b);
res-=(Lli)-pars[a]*(-pars[a]-1);
res-=(Lli)-pars[b]*(-pars[b]-1);
res-=(Lli)-pars[a]*incs[a].size();
res-=(Lli)-pars[b]*incs[b].size();
for(auto c:incs[b]){
outs[c].erase(b);
if(fnd(c)!=a){
outs[c].insert(a);
incs[a].insert(c);
}
}
for(auto c:mems[b]){
for(auto it=outs[c].begin();it!=outs[c].end();){
I d=*it;
if(d==a){
it=outs[c].erase(it);
incs[a].erase(c);
}
}
mems[a].push_back(c);
}
pars[a]+=pars[b],pars[b]=a;
res+=(Lli)-pars[a]*(-pars[a]-1);
res+=(Lli)-pars[a]*incs[a].size();
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I n,m;cin>>n>>m;
for(I i=0;i<m;i++){
I a,b;cin>>a>>b,a--,b--;
fols[i]={a,b};
}
fill_n(pars,n,-1);
for(I i=0;i<n;i++)mems[i].push_back(i);
for(I i=0;i<m;i++){
auto[a,b]=fols[i];
if(viss.count({b,a})){
uni(a,b);
}else{
viss.insert({a,b});
b=fnd(b);
if(!outs[a].count(b)){
outs[a].insert(b);
incs[b].insert(a);
res+=-pars[b];
}
}
printf("%lli\n",res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
11988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
11988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
11988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
