제출 #605221

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

joitter2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000007
#define N 200007
#define endl '\n'

ll n,M,f[100007],res,sz[100007],a[100007];

set<ll>s[100007],p[100007],d[100007];
set<ll>k;

map<ll,ll>m[100007];

ll P(ll x){
    if(f[x]!=x)f[x]=P(f[f[x]]);
    return f[x];
}

void A(ll x,ll y){
    if(p[x].size()<p[y].size()){
        swap(x,y);
    }
    //cout<<x<<" "<<y<<" "<<a[x]<<" "<<a[y]<<" "<<sz[x]<<" "<<sz[y]<<endl;
    res-=a[x]*sz[x];
    res-=a[y]*sz[y];
    res-=sz[x]*(sz[x]-1);
    res-=sz[y]*(sz[y]-1);
    sz[x]+=sz[y];
    res+=sz[x]*(sz[x]-1);
    for(auto it:s[y]){
        if(P(it)!=x){
            s[x].insert(P(it));
        }
    }
    k.clear();
    a[x]=0;
    for(auto it:p[x]){
        if(P(it)!=x && P(it)!=y){
            a[x]++;
            k.insert(it);
        }
    }
    swap(p[x],k);
    for(auto it:p[y]){
        if(p[x].count(it)==0 && P(it)!=x && P(it)!=y){
            a[x]++;
            p[x].insert(it);
        }
    }
    for(auto it:d[y]){
        if(P(it)!=x){
            s[P(it)].insert(x);
            d[x].insert(P(it));
        }
    }
    res+=a[x]*sz[x];
    f[y]=x;
    return ;
}

int main()
{
    cin>>n>>M;
    for(int i=1;i<=n;i++){
        f[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=M;i++){
        ll x,y;
        cin>>x>>y;
        if(P(x)!=P(y)){
            //cout<<P(y)<<" "<<P(x)<<" "<<s[P(x)].count(P(y))<<endl;
            ll fl=0;
            for(auto it:s[P(x)]){
                if(P(it)==P(y)){
                    fl=1;
                    break;
                }
            }
            if(fl==1)A(P(x),P(y));
            else{
                if(p[P(y)].count(x)==0){
                    res+=sz[P(y)];
                    p[P(y)].insert(x);
                    a[P(y)]++;
                }
                m[P(x)][P(y)]++;
                s[P(y)].insert(P(x));
                d[P(x)].insert(P(y));
            }
        }
        cout<<res<<endl;

    }

    return 0;
}

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