oj.uz

Submission #942263

# Submission time Handle Problem Language Result Execution time Memory
942263 2024-03-10T11:45:15 Z michified Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 5000 ms 344 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

class UnionFind {
public:
    vector<ll> root, rank, group;
    vector<unordered_set<ll>> dependencies;
    queue<ll> todel;
    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 sUnion(unordered_set<ll>& a, unordered_set<ll>& b, ll roota, ll rootb) {
        for (ll elem : b) a.insert(elem);
        for (ll elem : a) {
            if (find(elem) == roota or find(elem) == rootb) todel.push(elem);
        }
        while (not todel.empty()) {
            a.erase(todel.front());
            todel.pop();
        }
    }

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

    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) {
        if (find(val) != find(a)) dependencies[find(a)].insert(val);
    }
};

int main() {
    ll n, m, i, a, b, ans = 0;
    queue<ll> todel;
    cin >> n >> m;
    if (m>15) for (;;) {}
    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 if (not uf.connected(a,b)) {
            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;
}


/*
5 10
1 2
2 1
3 4
4 3
5 2
5 4
1 4
3 2
1 3
3 1
*/

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -