Submission #1058035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058035		mickey080929	Telephone Plans (CCO24_day2problem3)	C++17	25 / 25	1252 ms	122316 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

set<ll> adj[500010];
ll sz[2000010];
ll id[2000010];

void dfs(ll x, ll p, ll nw) {
    id[x] = nw;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        dfs(y, x, nw);
    }
}

ll getSize(ll x, ll p) {
    ll ret = 1;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        ret += getSize(y, x);
    }
    return ret;
}

ll add[1500010];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll E;
    cin >> E;
    ll N, Q;
    cin >> N >> Q;
    for (ll i=1; i<=N; i++) {
        id[i] = i;
        sz[i] = 1;
    }
    ll pv = N;
    ll prv = 0;
    ll cur = 0;
    for (ll q=1; q<=Q; q++) {
        if (q != 1) add[q-1] = add[q-2];
        ll cmd;
        cin >> cmd;
        if (cmd == 1) {
            ll x, y;
            cin >> x >> y;
            if (E) {
                x ^= prv;
                y ^= prv;
            }
            if (sz[id[x]] < sz[id[y]]) swap(x, y);
            cur -= sz[id[x]] * (sz[id[x]]-1) / 2;
            cur -= sz[id[y]] * (sz[id[y]]-1) / 2;
            sz[id[x]] += sz[id[y]];
            cur += sz[id[x]] * (sz[id[x]]-1) / 2;
            dfs(y, -1, id[x]);
            adj[x].insert(y);
            adj[y].insert(x);
        }
        else if (cmd == 2) {
            ll x, y;
            cin >> x >> y;
            if (E) {
                x ^= prv;
                y ^= prv;
            }
            adj[x].erase(y);
            adj[y].erase(x);
            ll cnt = 1;
            vector<array<ll,3>> stx, sty;
            stx.push_back({x, -1, -1});
            sty.push_back({y, -1, -1});
            while (true) {
                while (!stx.empty()) {
                    ll vtx = stx.back()[0];
                    ll par = stx.back()[1];
                    ll lo = stx.back()[2];
                    stx.pop_back();
                    auto it = adj[vtx].upper_bound(lo);
                    if (it == adj[vtx].end()) continue;
                    if (*it == par)
                        it = adj[vtx].upper_bound(par);
                    if (it == adj[vtx].end()) continue;
                    stx.push_back({vtx, par, *it});
                    stx.push_back({*it, vtx, -1});
                    break;
                }
                while (!sty.empty()) {
                    ll vtx = sty.back()[0];
                    ll par = sty.back()[1];
                    ll lo = sty.back()[2];
                    sty.pop_back();
                    auto it = adj[vtx].upper_bound(lo);
                    if (it == adj[vtx].end()) continue;
                    if (*it == par)
                        it = adj[vtx].upper_bound(par);
                    if (it == adj[vtx].end()) continue;
                    sty.push_back({vtx, par, *it});
                    sty.push_back({*it, vtx, -1});
                    break;
                }
                if (stx.empty() || sty.empty()) break;
                cnt ++;
            }
            if (stx.empty()) {
                swap(x, y);
            }
            ll szx = sz[id[x]] - cnt;
            ll szy = cnt;
            dfs(y, -1, ++pv);
            sz[id[x]] = szx;
            sz[id[y]] = szy;
            add[q-1] += szx * szy;
            cur -= szx * szy;
        }
        else {
            ll t;
            cin >> t;
            if (E) {
                t ^= prv;
            }
            ll ans = cur;
            if (q-t == 0) ans += add[q-1];
            else ans += add[q-1] - add[q-t-1];
            cout << ans << '\n';
            prv = ans;
        }
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 2 / 2
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5