#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,pas,t,tes,msh[100009];
map <long long, bool> mp[100009];
map <long long, vector <long long> > M[100009];
vector <long long> V[100009];
multiset <long long> in[100009],out[100009];
multiset <long long>::iterator it,tt;
bool check(long long q, long long w){
multiset <long long>::iterator it;
it=out[w].lower_bound(q);
if(it==out[w].end()||(*it)!=q) return 0; else return 1;
}
void ADD(long long q, long long w){
long long Q=q,W=w;
q=msh[q];w=msh[w];
if(q==w) return;
if(check(q,w)==0){
if(mp[Q][w]==0){
out[q].insert(w);
in[w].insert(q);
pas+=V[w].size();
mp[Q][w]=1;
M[q][w].push_back(Q);
}
return;
}
if(V[q].size()+in[q].size()+out[q].size()<V[w].size()+in[w].size()+out[w].size()) swap(q,w);//shedareba sadac kidev unda daamato wevrebi(sizes)
//
vector <pair <long long, long long> > NXT;
long long shida=0,gare=0;
long long qw=in[q].size();
for(it=in[w].begin(); it!=in[w].end(); it++){
if((*it)==q){
pas-=V[w].size();
tt=out[q].lower_bound(w);
out[q].erase(tt);
continue;
}
//
c=M[(*it)][w].back();
M[(*it)][w].pop_back();
if(mp[c][q]==0){
mp[c][q]=1;
pas+=V[q].size();
tt=out[(*it)].lower_bound(w);
out[(*it)].erase(tt);
out[(*it)].insert(q);
in[q].insert((*it));
}else{
gare++;
}
//
if(check((*it),q)==1) NXT.push_back({(*it),q});
}
for(it=out[w].begin(); it!=out[w].end(); it++){
if((*it)==q){
pas-=V[q].size();shida++;
tt=in[q].lower_bound(w);
in[q].erase(tt);
continue;
}
if(check(q,(*it))==1) NXT.push_back({q,(*it)});
tt=in[(*it)].lower_bound(w);
in[(*it)].erase(tt);
in[(*it)].insert(q);
out[q].insert((*it));
}
long long we=V[w].size();
pas+=(qw-shida-gare)*we;
//
in[w].clear();out[w].clear();
pas-=V[q].size()*(V[q].size()-1);
pas-=V[w].size()*(V[w].size()-1);
for(vector <long long>::iterator ITT=V[w].begin(); ITT!=V[w].end(); ITT++){
V[q].push_back((*ITT));msh[(*ITT)]=q;
}
pas+=V[q].size()*(V[q].size()-1);
V[w].clear();
while(NXT.size()){
ADD(NXT.back().first,NXT.back().second);
NXT.pop_back();
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>tes;
for(i=1; i<=a; i++){
msh[i]=i;V[i].push_back(i);
}
for(t=1; t<=tes; t++){
cin>>c>>d;
ADD(c,d);
cout<<pas<<"\n";
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void ADD(long long int, long long int)':
joitter2.cpp:15:19: warning: unused variable 'W' [-Wunused-variable]
15 | long long Q=q,W=w;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
21460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
21460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
21460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
