제출 #734273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734273		mosiashvililuka	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	5053 ms	16732 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,t,tes,msh[100009],pas,C,D;
vector <long long> V[100009];
set <long long> in[100009],out[100009],sm[100009];//sm-c ideashi in-ebia ogond komponentis magivrad wveros nomers agdeb
set <long long>::iterator it,tt;
bool check(long long q, long long w){
    if(out[w].find(q)==out[w].end()) return 0; else return 1;
}
void mrg(long long Q, long long W){
    long long q=msh[Q],w=msh[W];
    if(q==w) return;
    if(V[q].size()<V[w].size()) swap(q,w);
    long long qw=V[q].size(),we=V[w].size(),Sq=sm[q].size(),Sw=sm[w].size();
    pas-=qw*(qw-1);
    pas-=we*(we-1);
    pas-=qw*Sq;
    pas-=we*Sw;
    //
    vector <pair <long long, long long> > NXT;
    for(vector <long long>::iterator IT=V[w].begin(); IT!=V[w].end(); IT++){
        V[q].push_back((*IT));
        tt=sm[q].find((*IT));
        if(tt!=sm[q].end()){
            sm[q].erase(tt);
        }
        msh[(*IT)]=q;
    }
    V[w].clear();
    for(it=sm[w].begin(); it!=sm[w].end(); it++){
        if(msh[(*it)]==q) continue;
        if(sm[q].find((*it))==sm[q].end()){
            sm[q].insert((*it));
        }
    }
    Sq=sm[q].size();
    pas+=(qw+we)*Sq;
    //
    for(it=in[w].begin(); it!=in[w].end(); it++){
        if((*it)==q) continue;
        out[(*it)].erase(out[(*it)].find(w));
        out[(*it)].insert(q);
        in[q].insert((*it));
        if(check((*it),q)) NXT.push_back({(*it),q});
    }
    for(it=out[w].begin(); it!=out[w].end(); it++){
        if((*it)==q) continue;
        in[(*it)].erase(in[(*it)].find(w));
        in[(*it)].insert(q);
        out[q].insert((*it));
        if(check(q,(*it))) NXT.push_back({(*it),q});
    }
    //
    in[w].clear();out[w].clear();sm[w].clear();
    pas+=V[q].size()*(V[q].size()-1);
    while(NXT.size()){
        mrg(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;
        c=msh[C],d=msh[D];
        if(c==d){
            cout<<pas<<"\n";
            continue;
        }
        if(check(c,d)==0){
            if(sm[d].find(C)!=sm[d].end()){
                cout<<pas<<"\n";
                continue;
            }
            pas+=V[d].size();
            in[d].insert(c);out[c].insert(d);
            sm[d].insert(C);
            cout<<pas<<"\n";
            continue;
        }
        in[d].insert(c);out[c].insert(d);
        sm[d].insert(C);
        pas+=V[d].size();
        mrg(c,d);
        cout<<pas<<"\n";
    }
    return 0;
}

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