This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxn=1e5+7;
int r[maxn];
int sz[maxn];
set<int>child[maxn],adj[maxn],radj[maxn];
queue<ii>q;
ll ans=0;
int n,t;
void insert_weak_connection(int x,int y)
{
adj[x].insert(y);
radj[y].insert(x);
if(adj[y].count(x)){
q.push({x,y});
}
}
int Find(int u)
{
return (u==r[u])?u:r[u]=Find(r[u]);
}
int dsu_size(int u)
{
return adj[u].size()+child[u].size()+radj[u].size();
}
void Union(int a,int b)
{
if(a==b)return;
if(dsu_size(a)<dsu_size(b))swap(a,b);
ans+=(1ll*sz[a]*child[b].size()+1ll*sz[b]*child[a].size());
sz[a]+=sz[b];
r[b]=a;
for(int i:child[b]){
if(child[a].count(i))ans-=sz[a];
else child[a].insert(i);
}
for(int i:adj[b]){
radj[i].erase(b);
insert_weak_connection(a,i);
}
for(int i:radj[b]){
adj[i].erase(b);
insert_weak_connection(i,a);
}
}
void sol(){
cin>>n>>t;
for(int i=1;i<=n;i++){
r[i]=i;
sz[i]=1;
child[i].insert(i);
}
while(t--){
int x,y;
cin>>x>>y;
y=Find(y);
if(Find(x)!=y&&!child[y].count(x)){
child[y].insert(x);
ans+=sz[y];
insert_weak_connection(Find(x),y);
while(q.size()){
auto[x,y]=q.front();
q.pop();
Union(Find(x),Find(y));
}
}
cout<<ans<<"\n";
}
}
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message (stderr)
joitter2.cpp: In function 'void sol()':
joitter2.cpp:71:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | auto[x,y]=q.front();
| ^
joitter2.cpp: At global scope:
joitter2.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |