Submission #734119

#	Time	Username	Problem	Language	Result	Execution time	Memory
734119		mosiashvililuka	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5059 ms	21460 KiB

joitter2

#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 (stderr)

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;
      |                   ^

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83