Submission #942058

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

joitter2

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

class UnionFind {
public:
    vector<ll> root, rank, group, 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;
            dependencies[i] = 0;
        }
    }

    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] += dependencies[roota] - 2;
                dependencies[roota] = 0;
            } else if (rank[rootb] < rank[roota]) {
                root[rootb] = roota;
                group[roota] += group[rootb];
                dependencies[roota] += dependencies[rootb] - 2;
                dependencies[rootb] = 0;
            } else {
                root[roota] = rootb;
                rank[rootb]++;
                group[rootb] += group[roota];
                dependencies[rootb] += dependencies[roota] - 2;
                dependencies[roota] = 0;
            }
        }
    }

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

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

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

    void updd(ll a, ll val) {
        dependencies[find(a)] += val;
    }
};

int main() {
    ll n, m, i, a, b, ans = 0, tmp;
    queue<ll> todel;
    bool found, found2;
    cin >> n >> m;
    vector<unordered_set<ll>> isfollowing(n + 1), followsof(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];

        // check if a and b are part of the same group
        found = false;
        for (ll neighbor : isfollowing[b]) {
            if (uf.connected(neighbor, a)) {
                if (found) todel.push(neighbor);
                found = true;
            }
        }
        while (not todel.empty()) {
            isfollowing[b].erase(todel.front());
            todel.pop();
        }

        // check if a has already been linked to the group that b is in
        found2 = false;
        for (ll neighbor : followsof[a]) {
            if (uf.connected(neighbor, b)) {
                if (found2) todel.push(neighbor);
                found2 = true;
            }
        }
        while (not todel.empty()) {
            followsof[a].erase(todel.front());
            todel.pop();
        }

        // link a to the group that b belongs in if it hasn't been linked before
        if (not found and not found2 and not uf.connected(a, b)) {
            ans += uf.getg(b); 
            isfollowing[b].insert(a);
            followsof[a].insert(b);
            uf.updd(b, 1);
        }

        found = false;
        for (ll neighbor : isfollowing[a]) {
            // join the two groups together if there is a mutual connection
            if (uf.connected(neighbor, b)) {
                if (found) {
                    todel.push(neighbor);
                    continue;
                }
                ans += (uf.getg(a) - 1) * uf.getg(b) + uf.getg(a) * (uf.getg(b) - 1);  // mutually connect everyone
                ans += uf.getg(a) * (uf.getd(b) - 1) + uf.getg(b) * (uf.getd(a) - 1); // connect dependencies
                found = true;
            }
        }
        while (not todel.empty()) {
            isfollowing[a].erase(todel.front());
            todel.pop();
        }
        if (found) uf.join(a, b);

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

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:67:32: warning: unused variable 'tmp' [-Wunused-variable]
   67 |     ll n, m, i, a, b, ans = 0, tmp;
      |                                ^~~

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