//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
vector<map<int,int>> S1,S2,R1,R2;
vector<set<int>> belong;
queue<pair<int,int>> q;
ll ans=0;
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
for(int i=0;i<n;i++){
belong[i].insert(i);
}
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool same(int a,int b){
return find(a)==find(b);
}
int sz(int x){
return -e[find(x)];
}
void sir1(int a,int b){
if(R1[a].size()<sz(b)){
for(auto it=R1[a].begin();it!=R1[a].end();){
if(find((*it).f)==b){
S1[(*it).f].erase(a);
it=R1[a].erase(it);
}
else{
it++;
}
}
}
else{
for(auto v:belong[b]){
if(R1[a].find(v)!=R1[a].end()){
R1[a].erase(v);
S1[v].erase(a);
}
}
}
}
void sir2(int a,int b){
if(R2[a].size()<S2[b].size()){
for(auto v:R2[a]){
if(S2[b].find(v.f)!=S2[b].end()){
q.push({v.f,b});
}
}
}
else{
for(auto v:S2[b]){
if(R2[a].find(v.f)!=R2[a].end()){
q.push({v.f,b});
}
}
}
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
ans+=2ll*sz(a)*sz(b)-1ll*S2[a][b]*sz(b)-1ll*S2[b][a]*sz(a);
//cout<<S2[a][b]<<' '<<sz(b)<<'\n';
//cout<<S2[b][a]<<' '<<sz(a)<<'\n';
//cout<<a+1<<' '<<b+1<<' '<<2ll*sz(a)*sz(b)-1ll*S2[a][b]*sz(b)-1ll*S2[b][a]*sz(a)<<'\n';
// clear (a,b) edges
S2[a].erase(b);
S2[b].erase(a);
R2[a].erase(b);
R2[b].erase(a);
sir1(a,b);
swap(a,b);
sir1(a,b);
//new one way edges
int cnt=0;
if(R1[a].size()>R1[b].size()) swap(a,b);
for(auto v:R1[a]){
if(R1[b].find(v.f)!=R1[b].end()){
cnt++;
}
}
ans+=1ll*((int)R1[a].size()-cnt)*sz(b)+1ll*((int)R1[b].size()-cnt)*sz(a);
//out<<a+1<<' '<<b+1<<' '<<1ll*((int)R1[a].size()-cnt)*sz(b)+1ll*((int)R1[b].size()-cnt)*sz(a)<<'\n';
//new scc edges
sir2(a,b);
swap(a,b);
sir2(a,b);
// merge
if(R1[a].size()>R1[b].size()) swap(a,b);
for(auto v:R1[a]){
if(R1[b].find(v.f)!=R1[b].end()){
S2[find(v.f)][b]--;
R2[b][find(v.f)]--;
}
}
if(S2[a].size()<S2[b].size()){
swap(S2[a],S2[b]);
}
for(auto v:S2[b]){
S2[a][v.f]+=v.s;
R2[v.f].erase(b);
R2[v.f][a]+=v.s;
}
if(R1[a].size()<R1[b].size()){
swap(R1[a],R1[b]);
}
for(auto v:R1[b]){
S1[v.f].erase(b);
S1[v.f][a]=1;
R1[a][v.f]=1;
}
if(R1[a].size()<R1[b].size()){
swap(R2[a],R2[b]);
}
for(auto v:R2[b]){
S2[v.f].erase(b);
S2[v.f][a]+=v.s;
R2[a][v.f]+=v.s;
}
e[a]+=e[b];
e[b]=a;
if(belong[a].size()<belong[b].size()){
swap(belong[a],belong[b]);
}
for(auto v:belong[b]){
belong[a].insert(v);
}
return true;
}
};
int main() {_
int n,m;
cin>>n>>m;
//assert(n==4 and m==6);
S1.resize(n);
S2.resize(n);
R1.resize(n);
R2.resize(n);
belong.resize(n);
DSU dsu(n);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
if(dsu.same(a,b)){
cout<<ans<<'\n';
continue;
}
int pa=dsu.find(a);
int pb=dsu.find(b);
if(S1[a].find(pb)!=S1[a].end()){
cout<<ans<<'\n';
continue;
}
S1[a][pb]++;
S2[pa][pb]++;
R1[pb][a]=1;
R2[pb][pa]++;
ans+=dsu.sz(pb);
//cout<<"-"<<'\n';
if(S2[pb].find(pa)!=S2[pb].end()){
//cout<<i+1<<' '<<pa+1<<' '<<pb+1<<'\n';
q.push({pa,pb});
while(!q.empty()){
auto tmp=q.front();
q.pop();
dsu.unite(tmp.f,tmp.s);
}
}
cout<<ans<<'\n';
}
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
Compilation message
joitter2.cpp: In member function 'void DSU::sir1(int, int)':
joitter2.cpp:42:24: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if(R1[a].size()<sz(b)){
| ~~~~~~~~~~~~^~~~~~
joitter2.cpp: In function 'void setIO(std::string)':
joitter2.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
