#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int par[100010];
vector<int>gv[100010];
int sz[100010];
set<int>rev[100010];
map<int,int>cnt[100010];
ll ans;
inline void uni(int x,int y)
{
if(sz[x]>sz[y])
swap(x,y);
vector<int>putv;
ans-=(ll)cnt[x][y]*sz[y]+(ll)cnt[y][x]*sz[x];
ans+=(ll)sz[x]*sz[y]*2;
ans+=sz[x]*((ll)rev[y].size()-cnt[x][y]-cnt[y][y]);
for(int t:rev[x])
{
if(par[t]==x||par[t]==y)
continue;
if(rev[y].find(t)==rev[y].end())
putv.eb(t);
else
ans-=sz[x];
}
for(int&t:putv)
{
rev[y].ep(t);
cnt[par[t]][y]++;
ans+=sz[y];
}
cnt[y][y]+=cnt[x][y];
sz[y]+=sz[x];
for(int&t:gv[x])
par[t]=y,gv[y].eb(t);
gv[x].clear();
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=0;i++<n;)
gv[par[i]=i].eb(i),sz[i]=1;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
if(par[u]!=par[v]&&rev[par[v]].find(u)==rev[par[v]].end())
{
ans+=sz[par[v]];
rev[par[v]].ep(u);
cnt[par[u]][par[v]]++;
if(cnt[par[v]][par[u]]>0)
uni(par[u],par[v]);
}
cout<<ans<<'\n';
}
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
