Submission #1271345

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

joitter2

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
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;
    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);
        // cout << "UNI: " << a << " " << b << endl;
        //samo vo starite
        ans -= (f(size[a]) + f(size[b]));
        //koga ke se spojat
        ans += f(size[a]+size[b]);

        if(a == 3 && b == 5) {
            // cout << size[a] << " " << size[b] << endl;
            // cout << "rem: " << f(size[a])+f(size[b]) << endl;
            // cout << "add: " << f(size[a]+size[b]) << endl;
        }
        // cout << "after p1: " << ans << endl;
        //directed edges
        set<int> vis;
        for(auto u : st[a]) {
            if(same_set(u, a)) continue;
            // vis.insert(u);
            // if(!same_set(b, u)) ans += size[b];
            // else ans -= size[a];
            if(!st[b].count(u)) {
                // if(a==3&&b==5)cout << "dir " << u << " to " << a << endl;
                if(!same_set(b, u)) ans += size[b];
                else ans -= size[a];
            }
        }
        for(auto u : st[b]) {
            if(same_set(u, b)) continue;
            // if(a==3&&b==5)cout << "dir " << u << " to " << b << endl;
            // vis.insert(u);
            // if(!same_set(a, u)) ans += size[a];
            // else ans -= size[b];
            if(!st[a].count(u)) {
                // if(a==3&&b==5)cout << "dir " << u << " to " << a << endl;
                if(!same_set(a, u)) ans += size[a];
                else ans -= size[b];
            }
        }
        // cout << "after p2: " << ans << endl;

        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);
        }

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

        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)) {
            // cout << "push " << a << " " << b << endl;
            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);
    }

    void print() {
        // for(int i=1; i<=n; i++) cout << par[i] << " ";
        // cout << endl;
        // cout << "print st: \n";
        // for(int i=1; i<=n; i++) {
        //     if(i != find(i)) continue;
        //     cout << i << ": ";
        //     for(int j : st[i]) cout << j << " ";
        //     cout << endl;
        // }
        // cout << "print in: \n";
        // for(int i=1; i<=n; i++) {
        //     if(i != find(i)) continue;
        //     cout << i << ": ";
        //     for(int j : in[i]) cout << j << " ";
        //     cout << endl;
        // }
        // cout << "print out: \n";
        // for(int i=1; i<=n; i++) {
        //     if(i != find(i)) continue;
        //     cout << i << ": ";
        //     for(int j : out[i]) cout << j << " ";
        //     cout << endl;
        // }
    }
};

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);
        // dsu.print();
        cout << dsu.ans << '\n';
    }
}

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