제출 #212566

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

joitter2

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


using LL = long long int;
using uLL = unsigned long long int;
using uint = unsigned int;
using ld = long double;

const int N = 100007;

int parent[N];
set <int> in[N], out[N], vert[N];
set <pair<int,int> > S;
queue <pair<int,int> > Q;
LL ans;


void init_UF(int n){
    for(int i = 1; i <= n; i++){
        parent[i] = i;
        vert[i].insert(i);
    }
}

inline LL newton(int n){
    return LL(n)*(n-1);
}


int FIND(int x){
    if(x == parent[x]) return x;
    return parent[x] = FIND(parent[x]);
}

void add_edge(int a, int b){
    int pa = FIND(a), pb = FIND(b);
    if(pa == pb) return;
    if(in[pb].find(a) == in[pb].end()){
        in[pb].insert(a);
        ans += vert[pb].size();
    }
    out[pa].insert(b);
    S.insert({pa, pb});
    if(S.find({pb, pa}) != S.end()){
        Q.push({pa, pb});
    }
}



void UNION(int a, int b){
    if(a == b) return;
    if(vert[a].size() > vert[b].size()) swap(a, b);
    parent[a] = b;
    S.erase({a, b});
    S.erase({b, a});
    ans -= LL(vert[b].size()) * in[b].size();
    ans -= LL(vert[a].size()) * in[a].size();
    ans -= newton(vert[a].size());
    ans -= newton(vert[b].size());
    for(auto x: vert[a]){
        if(in[b].find(x) != in[b].end()){
            in[b].erase(x);
        }
        if(out[b].find(x) != out[b].end()){
            out[b].erase(x);
        }
        vert[b].insert(x);
    }
    vert[a].clear();
    for(auto x: in[a]){
        if(vert[b].find(x) != vert[b].end()) continue;
        int y = FIND(x);
        S.erase({y, a});
        S.insert({y, b});
        if(S.find({b, y}) != S.end()){
            Q.push({b, y});
        }
        in[b].insert(x);
    }
    in[a].clear();
    for(auto x: out[a]){
        if(vert[b].find(x) != vert[b].end()) continue;
        int y = FIND(x);
        S.erase({a, y});
        S.insert({b, y});
        if(S.find({y, b}) != S.end()){
            Q.push({b, y});
        }
        out[b].insert(x);
    }
    out[a].clear();
    /*cout << "LOL " << vert[b].size() << " " << in[b].size() << '\n';
    for(auto x: in[b]) cout << x << " ";
    cout << '\n';
    for(auto x: vert[b]) cout << x << " ";
    cout << '\n';*/
    ans += LL(vert[b].size()) * in[b].size();
    ans += newton(vert[b].size());
}



void update(){
    while(!Q.empty()){
        pair<int,int> x = Q.front();
        Q.pop();
        UNION(FIND(x.first), FIND(x.second));
    }
}



int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    init_UF(n);
    while(q--){
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
        update();
        cout << ans << '\n';
    }
    
    
    
    return 0;
}

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