Submission #1271346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271346		VMaksimoski008	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	17 / 100	5095 ms	87664 KiB

joitter2

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

const int N = 3e5 + 5;

set<int> st[N], in[N], out[N];

inline ll f(ll x) {
    return x * (x - 1);
}

struct union_find {
    int n;
    vector<int> par, size, to_rem;
    vector<pii> ord;
    ll ans = 0;

    union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

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

    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);

        ans -= (f(size[a]) + f(size[b]));
        ans += f(size[a]+size[b]);

        for(auto u : st[a]) {
            if(same_set(u, a)) continue;
            if(!st[b].count(u)) {
                if(!same_set(b, u)) ans += size[b];
                else ans -= size[a];
            }
        }
        for(auto u : st[b]) {
            if(same_set(u, b)) continue;
            if(!st[a].count(u)) {
                if(!same_set(a, u)) ans += size[a];
                else ans -= size[b];
            }
        }

        if(out[a].count(b)) out[a].erase(b);
        if(out[b].count(a)) out[b].erase(a);
        if(in[a].count(b)) in[a].erase(b);
        if(in[b].count(a)) in[b].erase(a);

        for(int u : out[b]) {
            in[u].erase(b);
            add_edge_g(a, u);
        }

        for(int u : in[b]) {
            out[u].erase(b);
            add_edge_g(u, a);
        }

        for(int u : st[b]) {
            if(!same_set(u, a)) st[a].insert(u);
        }

        for(int u : st[a])
            if(same_set(u, b)) to_rem.push_back(u);
        for(int u : to_rem) st[a].erase(u);

        to_rem.shrink_to_fit();
        to_rem.clear();

        par[b] = a;
        size[a] += size[b];
    }

    void check(int a, int b) {
        if(same_set(a, b)) return ;
        if(in_comp(b, a)) return ;

        ans += get_size(b);
        add_edge_st(b, a);

        add_edge_g(a, b);

        while(!ord.empty()) {
            auto [u, v] = ord.back();
            ord.pop_back();
            uni(u, v);
        }
    }

    void add_edge_g(int a, int b) {
        a = find(a); b = find(b);

        out[a].insert(b);
        in[b].insert(a);

        if(out[a].count(b) && out[b].count(a)) {
            ord.push_back({ a, b });
        }
    }

    void add_edge_st(int a, int b) {
        st[find(a)].insert(b);
    }

    bool in_comp(int a, int b) {
        return st[find(a)].count(b);
    }

    int get_size(int a) {
        return size[find(a)];
    }

    bool same_set(int a, int b) {
        return find(a) == find(b);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, m; cin >> n >> m;
    union_find dsu(n);

    while(m--) {
        int a, b; cin >> a >> b;
        dsu.check(a, b);
        cout << dsu.ans << '\n';
    }
}

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