Submission #1070650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070650		BF001	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	707 ms	68176 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define fi first
#define se second
#define int long long

typedef pair<int, int> ii; 

int n, m, res, siz[N], par[N];
set<int> child[N], adj[N], r_adj[N];
queue<ii> q; 

int find(int u){
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void addeg(int u, int v){
    adj[u].insert(v);
    r_adj[v].insert(u);
    if (adj[v].count(u)) q.push({u, v});
}

int sum(int u){
    return child[u].size() + adj[u].size() + r_adj[u].size();
}

void unin(int u, int v){
    u = find(u);
    v = find(v);
    if (u == v) return;
    res += child[u].size() * siz[v] + child[v].size() * siz[u];
    if (sum(u) < sum(v)) swap(u, v);
    siz[u] += siz[v];
    par[v] = u;
    for (auto x : child[v]){
        if (child[u].find(x) != child[u].end()) res -= siz[u];
        else child[u].insert(x);
    }
    adj[u].erase(v);
    r_adj[u].erase(v);
    adj[v].erase(u);
    r_adj[v].erase(u);
    for (auto x : adj[v]){
        r_adj[x].erase(v);
        addeg(u, x);
    }
    for (auto x : r_adj[v]){
        adj[x].erase(v);
        addeg(x, u);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        siz[i] = 1;
        par[i] = i;
        child[i].insert(i);
    }

    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        v = find(v);
        if (find(u) != v && child[v].find(u) == child[v].end()){
            child[v].insert(u);
            res += siz[v];
            u = find(u);
            addeg(u, v);
            while (!q.empty()){
                int u = q.front().fi;
                int v = q.front().se;
                unin(u, v);
                q.pop();
            }
        }
        cout << res << "\n";
    }
 
    return 0;
}

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