Submission #1217007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217007		vanea	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	893 ms	65800 KiB

joitter2

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

const int mxN = 1e5+10;

set<int> adj[mxN], rev_adj[mxN], child[mxN];
int p[mxN];
ll ans = 0, sz[mxN];
queue<pair<int, int>> to_merge;

int get(int x) {
    return p[x] == x ? x : p[x] = get(p[x]);
}

void add(int a, int b) {
    adj[a].insert(b);
    rev_adj[b].insert(a);
    if(adj[b].count(a)) {
        to_merge.push({a, b});
    }
}

int dsu_size(int a) {
    return child[a].size() + adj[a].size() + rev_adj[a].size();
}

void uni(int a, int b) {
    if(a == b) return ;
    if(dsu_size(a) < dsu_size(b)) swap(a, b);

    ans += sz[b] * child[a].size() + sz[a] * child[b].size();

    sz[a] += sz[b];
    p[b] = a;

    for(auto it : child[b]) {
        if(child[a].count(it)) ans -= sz[a];
        else child[a].insert(it);
    }
    adj[a].erase(b); rev_adj[a].erase(b);
    adj[b].erase(a); rev_adj[b].erase(a);
    for(auto it : adj[b]) {
        rev_adj[it].erase(b);
        add(a, it);
    }
    for(auto it : rev_adj[b]) {
        adj[it].erase(b);
        add(it, a);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
        child[i].insert(i);
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        b = get(b);
        if(get(a) != b && !child[b].count(a)) {
            child[b].insert(a);
            ans += sz[b];
            a = get(a);
            add(a, b);
            while(!to_merge.empty()) {
                tie(a, b) = to_merge.front();
                to_merge.pop();
                uni(get(a), get(b));
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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