Submission #824174

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

joitter2

#include <bits/stdc++.h>
using namespace std;
// 123

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, m;
        cin >> n >> m;
        vector<set<pair<int, int>>> g(n), rg(n);
        vector<int> par(n, -1);
        int64_t ans = 0;
        queue<pair<int, int>> q;

        function<int(int)> root = [&](int u) { return par[u] < 0 ? u : par[u] = root(par[u]); };
        function<int(set<pair<int, int>>&, int)> cnt = [&](set<pair<int, int>>& s, int u) {
                auto it = s.lower_bound(make_pair(u, -1));
                int res = 0;
                while (it != s.end() && it->first == u) {
                        res++, it = s.erase(it);
                }
                return res;
        };
        function<void(int, int)> check = [&](int u, int v) {
                auto it = g[u].lower_bound(make_pair(v, -1));
                if (it != g[u].end() && it->first == v) q.emplace(u, v);
        };
        function<void(int, int)> unite = [&](int u, int v) {
                u = root(u), v = root(v);
                if (u == v) return;

                cnt(g[u], v), cnt(g[v], u);

                ans += 1ll * cnt(rg[v], u) * par[v];
                ans += 1ll * cnt(rg[u], v) * par[u];
                ans += 2ll * par[u] * par[v];
                ans -= 1ll * rg[v].size() * par[u];
                ans -= 1ll * rg[u].size() * par[v];

                if (rg[u].size() + g[u].size() < rg[v].size() + g[v].size()) swap(u, v);
                for (auto x : rg[v]) {
                        if (rg[u].find(x) != rg[u].end()) ans += par[u] + par[v];
                }

                par[u] += par[v];
                par[v] = u;

                for (auto x : rg[v]) rg[u].emplace(x);
                for (auto x : g[v]) g[u].emplace(x);

                for (auto [x, y] : g[v]) {
                        auto it = rg[x].lower_bound(make_pair(v, -1));
                        while (it != rg[x].end() && it->first == v) {
                                rg[x].emplace(u, it->second);
                                it = rg[x].erase(it);
                        }
                }

                for (auto [x, y] : rg[v]) {
                        auto it = g[x].lower_bound(make_pair(v, -1));
                        while (it != g[x].end() && it->first == v) {
                                g[x].emplace(u, it->second);
                                it = g[x].erase(it);
                        }
                }

                for (auto [x, y] : g[v]) {
                        check(x, v);
                }

                for (auto [x, y] : rg[v]) {
                        check(v, x);
                }
        };

        for (int i = 0; i < m; i++) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                int a = root(u), b = root(v);
                if (a != b) {
                        g[a].emplace(b, v);
                        ans -= rg[b].emplace(a, u).second * par[b];
                        check(b, a);

                        while (q.size()) {
                                auto [x, y] = q.front();
                                q.pop();
                                unite(x, y);
                        }
                }
                cout << ans << '\n';
        }
}

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