Submission #945158

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

joitter2

#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;
    bool found;
    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);
            for (ll elem : f[curb]) {
                f[cura].insert(elem);
                rf[elem].insert(cura);
                if (isin(cura, f[elem]) and elem != cura) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : rf[curb]) {
                f[elem].insert(cura);
                f[elem].erase(curb);
                rf[cura].insert(elem);
                if (isin(elem, f[cura]) and elem != cura) tomerge.push(make_pair(elem, cura));
            }
            for (ll elem : A[curb]) root[elem] = cura;
        }
        cout << ans << endl;
    }
    return 0;
}


/*
5 6
1 2
2 3
3 4
4 5
5 1
2 1
*/

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:11:10: warning: unused variable 'found' [-Wunused-variable]
   11 |     bool found;
      |          ^~~~~

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