Submission #924814

#	Time	Username	Problem	Language	Result	Execution time	Memory
924814		alexander707070	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	4 ms	17500 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;
unordered_set<int> to[MAXN];
bool dali;
 
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    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;

        dali=false;
        if(to[a].find(comp[b])==to[a].end())dali=true;
        to[a].insert(comp[b]);

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


        if(dali){
            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]){
                r[i].erase(b);
 
                v[a].insert(i);
                r[i].insert(a);
 
                if(r[a].find(i)!=r[a].end()){
                    q.push(i);
                }
            }
            v[b].clear();
 
            for(int i:r[b]){
                v[i].erase(b);

                dali=true;
                for(int f:ver[i]){
                    if(to[f].find(b)!=to[f].end() and to[f].find(a)!=to[f].end()){
                        to[f].erase(b); 
                        dali=false; break;
                    }
                }

                if(dali){
                    r[a].insert(i);
                    v[i].insert(a);
    
                    if(v[a].find(i)!=v[a].end()){
                        q.push(i);
                    }
                }
            }
            r[b].clear();
 
            for(int i:ver[b]){
                ver[a].push_back(i);
                comp[i]=a;
            }
            ver[b].clear();
 
            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;
}

/*
5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3


*/

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