제출 #924582

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

joitter2

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

int n,m,a,b,x,y,ans;
int comp[MAXN],sz[MAXN];
vector<int> ver[MAXN];
multiset<int> v[MAXN],r[MAXN];
queue<int> q;

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        comp[i]=i; sz[i]=1;
        ver[i]={i};
    }

    for(int i=1;i<=m;i++){
        cin>>a>>b;
        a=comp[a]; b=comp[b];

        if(a==b){
            cout<<ans<<"\n";
            continue;
        }

        v[a].insert(b);
        r[b].insert(a);
        ans+=sz[b];

        if(v[b].find(a)==v[b].end()){
            cout<<ans<<"\n";
            continue;
        }

        q.push(b);

        while(!q.empty()){
            b=q.front();
            q.pop();

            if(sz[b]==0)continue;
            if(v[a].size()+r[a].size()+ver[a].size() < v[b].size() + r[b].size() + ver[b].size())swap(a,b);

            ans-=sz[a]*(sz[a]-1);
            ans-=sz[b]*(sz[b]-1);

            ans-=int(r[a].size())*sz[a];
            ans-=int(r[b].size())*sz[b];

            v[a].erase(b);
            r[b].erase(a);

            v[b].erase(a);
            r[a].erase(b);

            for(int i:v[b]){
                cout<<"out "<<i<<"\n";
                r[i].erase(b);

                v[a].insert(i);
                r[i].insert(a);

                if(r[a].find(i)!=r[a].end()){
                    q.push(i);
                    cout<<"adding "<<i<<"\n";
                }
            }
            v[b].clear();

            for(int i:r[b]){
                cout<<"in "<<i<<"\n";
                v[i].erase(b);

                r[a].insert(i);
                v[i].insert(a);

                if(v[a].find(i)!=v[a].end()){
                    q.push(i);
                    cout<<"adding "<<i<<"\n";
                }
            }
            r[b].clear();

            for(int i:ver[b]){
                ver[a].push_back(i);
                comp[i]=a;
            }
            ver[b].clear();

            cout<<ans<<":";

            sz[a]+=sz[b]; sz[b]=0;
            ans+=sz[a]*(sz[a]-1);
            ans+=int(r[a].size())*sz[a];
        }

        cout<<ans<<"\n";
    }

    return 0;
}

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