#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
set<pair<int,int>> adj[100000], radj[100000];
int color[100000], cnt[100000];
long long ans;
int find_(int a) {return color[a]=a==color[a] ? a:find_(color[a]);}
void erase_value(int a, int b, set<pair<int,int>> *adj)
{
auto L=adj[a].lower_bound({b,0}), R=adj[a].upper_bound({b,0x7fffffff});
while(L!=R) {
auto temp=L++;
adj[a].erase(temp);
}
}
void replace_value(int c, int a, int b, set<pair<int,int>> *adj)
{
auto L=adj[c].lower_bound({b,0}), R=adj[c].upper_bound({b,0x7fffffff});
vector<pair<int,int>> T;
while(L!=R) {
auto temp=L++;
T.emplace_back(a,temp->second);
adj[c].erase(temp);
}
for(auto t: T) adj[c].insert(t);
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
if(a==b) return;
if(adj[a].size()+radj[a].size()<adj[b].size()+radj[b].size()) swap(a,b);
ans-=cnt[a]*(adj[a].size()+cnt[a]-1LL)+cnt[b]*(adj[b].size()+cnt[b]-1LL);
color[b]=a;
cnt[a]+=cnt[b];
erase_value(a,b,adj); erase_value(b,a,adj);
erase_value(a,b,radj); erase_value(b,a,radj);
for(auto n: adj[b]) {
replace_value(n.first,a,b,radj);
adj[a].insert(n);
}
for(auto n: radj[b]) {
replace_value(n.first,a,b,adj);
radj[a].insert(n);
}
ans+=cnt[a]*(adj[a].size()+cnt[a]-1LL);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
cin>>N>>M;
for(int i=0;i<N;i++) cnt[color[i]=i]=1;
while(M--) {
int a, b, x, y;
cin>>a>>b;
if((x=find_(--a))==(y=find_(--b)) || adj[y].find({x,a})!=adj[y].end()) {
cout<<ans<<'\n';
continue;
}
adj[y].emplace(x,a);
radj[x].emplace(y,b);
ans+=cnt[y];
auto it=adj[x].lower_bound({y,0});
if(adj[x].find({y,b})!=adj[x].end()) union_(a,b);
cout<<ans<<'\n';
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:81:8: warning: variable 'it' set but not used [-Wunused-but-set-variable]
81 | auto it=adj[x].lower_bound({y,0});
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
