Submission #942098

#	Time	Username	Problem	Language	Result	Execution time	Memory
942098		michified	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	0 ms	344 KiB

joitter2

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

unordered_set<ll>& sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll one, ll two) {
    if (a.size() > b.size()) {
        for (ll elem : b) a.insert(elem);
        a.erase(one);
        a.erase(two);
        return a;
    }
    for (ll elem : a) b.insert(elem);
    b.erase(one);
    b.erase(two);
    return b;
}

inline ll combs(ll a) {
    return (a - 1) * a;
}

class UnionFind {
public:
    vector<ll> root, rank, group;
    vector<unordered_set<ll>> dependencies;
    UnionFind(ll n) {
        root.resize(n);
        rank.resize(n);
        group.resize(n);
        dependencies.resize(n);
        for (ll i = 0; i < n; i++) {
            root[i] = i;
            rank[i] = 1;
            group[i] = 1;
        }
    }

    ll find(ll a) {
        if (root[a] == a) return a;
        return root[a] = find(root[a]);
    }

    void join(ll a, ll b){
        ll roota = find(a), rootb = find(b);
        if (roota != rootb) {
            if (rank[roota] < rank[rootb]) {
                root[roota] = rootb;
                group[rootb] += group[roota];
                dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
            } else if (rank[rootb] < rank[roota]) {
                root[rootb] = roota;
                group[roota] += group[rootb];
                dependencies[roota] = sUnion(dependencies[roota], dependencies[rootb], a, b);
            } else {
                root[roota] = rootb;
                rank[rootb]++;
                group[rootb] += group[roota];
                dependencies[rootb] = sUnion(dependencies[roota], dependencies[rootb], a, b);
            }
        }
    }

    inline bool connected(ll a, ll b) {
        return find(a) == find(b);
    }

    inline ll getg(ll a) {
        return group[find(a)];
    }

    inline ll getd(ll a) {
        return dependencies[find(a)].size();
    }

    inline void updd(ll a, ll val) {
        dependencies[find(a)].insert(val);
    }
};

int main() {
    ll n, m, i, a, b, ans = 0;
    queue<ll> todel;
    cin >> n >> m;
    vector<unordered_set<ll>> isfollowing(n + 1);
    UnionFind uf(n + 1);
    vector<vector<ll>> queries(m, vector<ll>(2));
    for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];

    for (i = 0; i < m; i++) {
        a = queries[i][0];
        b = queries[i][1];

        if (isfollowing[b].find(a) == isfollowing[b].end()) {
            ans -= uf.getd(b) * uf.getg(b);
            uf.updd(b, a);
            ans += uf.getd(b) * uf.getg(b);
        } else {
            ans -= combs(uf.getg(a));
            ans -= combs(uf.getg(b));
            ans -= uf.getd(a) * uf.getg(a);
            ans -= uf.getd(b) * uf.getg(b);
            uf.join(a, b);
            ans += combs(uf.getg(a));
            ans += uf.getd(a) * uf.getg(a);
        }
        isfollowing[a].insert(b);

        cout << ans << endl;
    }
    return 0;
}

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