oj.uz

Submission #945176

# Submission time Handle Problem Language Result Execution time Memory
945176 2024-03-13T13:35:37 Z michified Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 4 ms 604 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline bool isin(ll a, unordered_set<ll>& s) {
    return s.find(a) != s.end();
}

int main() {
    ll n, m, i, a, b, ans = 0;
    cin >> n >> m;
    vector<vector<ll>> queries(m, vector<ll>(2));
    for (i = 0; i < m; i++) cin >> queries[i][0] >> queries[i][1];
    vector<unordered_set<ll>> A(n + 1), AB(n + 1), f(n + 1), rf(n + 1);
    vector<ll> root(n + 1);
    queue<pair<ll, ll>> tomerge;
    ll cura, curb;
    for (i = 0; i <= n; i++) {
        A[i].insert(i);
        AB[i].insert(i);
        root[i] = i;
    }

    for (i = 0; i < m; i++) {
        a = queries[i][0];
        b = queries[i][1];
        f[root[a]].insert(root[b]);
        rf[root[b]].insert(root[a]);
        if (not isin(a, AB[root[b]])) {
            AB[root[b]].insert(a);
            ans += A[root[b]].size();
        }
        if (isin(root[a], f[root[b]]) and root[a] != root[b]) tomerge.push(make_pair(root[a], root[b]));
        while (not tomerge.empty()) {
            cura = tomerge.front().first;
            curb = tomerge.front().second;
            tomerge.pop();
            ans -= A[cura].size() * (AB[cura].size() - 1);
            ans -= A[curb].size() * (AB[curb].size() - 1);
            if (AB[cura].size() < AB[curb].size()) swap(cura, curb);
            for (ll elem : AB[curb]) AB[cura].insert(elem);
            for (ll elem : A[curb]) A[cura].insert(elem);
            ans += A[cura].size() * (AB[cura].size() - 1);
            f[cura].erase(curb);
            for (ll elem : f[curb]) {
                if (elem == cura) {
                    rf[cura].erase(curb);
                    continue;
                }
                f[cura].insert(elem);
                rf[elem].insert(cura);
                rf[elem].erase(curb);
                if (isin(cura, f[elem])) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : rf[curb]) {
                if (elem == cura) continue;
                f[elem].insert(cura);
                f[elem].erase(curb);
                rf[cura].insert(elem);
                if (isin(elem, f[cura])) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : A[curb]) root[elem] = cura;
        }
        cout << ans << endl;
    }
    return 0;
}


/*
8 14
1 2
2 1
3 4
4 3
5 6
6 5
7 8
8 7
1 5
1 3
6 3
4 8
7 6
3 2
*/

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 4 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 4 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 4 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -