Submission #979030

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

joitter2

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

ll get(int l, int r = -1) {
    if (r == -1) return 1ll * l * (l + 1) / 2;
    return 1ll * (r - l + 1) * (l + r) / 2;
}

void solve() {
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    vector<vector<int>> have(n + 1);
    vector<set<int>> in(n + 1), out(n + 1);
    set<pair<int, int>> adj;
    vector<int> weight(n + 1, 2), par(n + 1);
    for (int i = 1; i <= n; i++) have[i].emplace_back(i);
    iota(par.begin(), par.end(), 0);
    auto merge = [&](auto &merge, int u, int v) -> void {
        u = par[u], v = par[v];
        if (weight[u] < weight[v]) swap(u, v);
        ans -= 1ll * have[u].size() * (have[u].size() - 1);
        ans -= 1ll * have[v].size() * (have[v].size() - 1);
        for (int x: in[u]) {
            ans -= have[u].size();
        }
        weight[u] -= have[u].size() + in[u].size();
        // cout << u << ' ' << v << endl;
        queue<pair<int, int>> q;
        for (int x: in[v]) {
            ans -= have[v].size();
            if (par[x] == u) {
                out[x].erase(v);
                weight[u]--;
                continue;
            }
                
            in[u].insert(x);

            if (adj.count(make_pair(par[x], v))) adj.erase(make_pair(par[x], v));
            adj.emplace(par[x], u);
            if (adj.count(make_pair(u, par[x]))) q.emplace(u, par[x]);

            out[x].erase(v);
            out[x].insert(u);
        }
        int old = have[u].size();
        for (int x: have[v]) {
            par[x] = u;
            have[u].emplace_back(x);
            vector<int> del;
            for (int y: out[x]) {
                if (y == u) {
                    del.emplace_back(y);
                    in[u].erase(x);
                } else if (adj.count(make_pair(par[y], u))) {
                    q.emplace(par[y], u);
                }
            }
            for (int y: del) out[x].erase(y);
            weight[u] += out[x].size();
        }
        weight[u] += have[u].size() + in[u].size();
        for (int x: in[u]) ans += have[u].size();
        ans += have[u].size() * (have[u].size() - 1);
        in[v].clear(), have[v].clear();
        while (!q.empty()) {
            auto [u, v] = q.front(); q.pop();
            merge(merge, u, v);
        }
    };
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (par[u] == par[v] or out[u].count(par[v])) {
            cout << ans << '\n';
            continue;
        }
        if (adj.count(make_pair(par[v], par[u]))) {
            merge(merge, u, v);
        } else {
            ans += have[par[v]].size();
            out[u].insert(par[v]);
            in[par[v]].insert(u);
            weight[par[u]]++, weight[par[v]]++;
            adj.emplace(par[u], par[v]);
        }
        cout << ans << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int queries = 1;

#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    // cin >> queries;

    for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
        cout << "Test case: " << test_case << endl;
#endif
        solve();
        cout << '\n';
    }

#ifdef sunnatov
    cout << "a";
#endif
}

Compilation message (stderr)

joitter2.cpp: In instantiation of 'solve()::<lambda(auto:23&, int, int)> [with auto:23 = solve()::<lambda(auto:23&, int, int)>]':
joitter2.cpp:81:30:   required from here
joitter2.cpp:25:18: warning: unused variable 'x' [-Wunused-variable]
   25 |         for (int x: in[u]) {
      |                  ^
joitter2.cpp:65:18: warning: unused variable 'x' [-Wunused-variable]
   65 |         for (int x: in[u]) ans += have[u].size();
      |                  ^
joitter2.cpp:48:13: warning: unused variable 'old' [-Wunused-variable]
   48 |         int old = have[u].size();
      |             ^~~

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