Submission #568078

#	Time	Username	Problem	Language	Result	Execution time	Memory
568078		alvingogo	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	2 ms	320 KiB

joitter2

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct no{
    int bo,sz;
    map<int,int> tb,fb;
    set<int> tp,fp;
    vector<int> ch;
};
vector<no> v;
long long ans=0;
int find(int a){
    return v[a].bo==a?a:v[a].bo=find(v[a].bo);
}
void merge(int x,int y){
    int a=find(x),b=find(y);
    //cout << a << " " << b << " " << v[a].sz << " " << v[b].sz << " " << v[a].tp.size() << " " << v[b].tp.size() << "\n";
    if(v[a].sz>v[b].sz){
        swap(a,b);
    }
    ans-=v[b].tp.size()*v[b].sz;
    ans-=v[a].tp.size()*v[a].sz;
    ans-=(v[b].sz)*(v[b].sz-1);
    ans-=(v[a].sz)*(v[a].sz-1);
    for(auto y:v[a].tp){
        int u=find(y);
        if(u==b){
            continue;
        }
        v[b].tp.insert(y);
        v[u].fb.erase(a);
        v[u].fb[b]++;
    }
    for(auto y:v[a].fp){
        int u=find(y);
        if(u==b){
            continue;
        }
        v[b].fp.insert(y);
        v[u].tb.erase(a);
        v[u].tb[b]++;
    }
    for(auto y:v[a].ch){
        if(v[b].tp.find(y)!=v[b].tp.end()){
            v[b].tp.erase(y);
        }
        v[b].ch.push_back(y);
    }
    v[b].sz+=v[a].sz;
    v[a].bo=b;
    ans+=v[b].tp.size()*v[b].sz;
    //cout << v[b].tp.size() << " " << v[b].sz << "\n";
    ans+=(v[b].sz)*(v[b].sz-1);
    set<int> nxt;
    for(auto y:v[a].tp){
        int u=find(y);
        if(u==b){
            continue;
        }
        if(v[u].tb.find(b)!=v[u].tb.end()){
            nxt.insert(u);
        }
    }
    for(auto y:v[a].fp){
        int u=find(y);
        if(u==b){
            continue;
        }
        if(v[u].fb.find(b)!=v[u].fb.end()){
            nxt.insert(u);
        }
    }
    for(auto y:v[a].tb){
        if(y.fs!=b){
            v[b].tb[y.fs]++;
        }
    }
    for(auto y:v[a].fb){
        if(y.fs!=b){
            v[b].fb[y.fs]++;
        }
    }
    for(auto h:nxt){
        merge(h,b);
    }
}
int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    v.resize(n);
    for(int i=0;i<n;i++){
        v[i].bo=i;
        v[i].sz=1;
        v[i].ch.push_back(i);
    }
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        int c=find(a),d=find(b);
        if(c==d){
            continue;
        }
        else{
            if(v[d].tp.find(a)==v[d].tp.end()){
                v[d].tp.insert(a);
                ans+=v[d].sz;
                v[d].tb[c]++;
                v[c].fb[d]++;
                v[c].fp.insert(b);
                if(v[c].tb.find(d)!=v[c].tb.end()){
                    merge(a,b);
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

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