Submission #900492

#	Time	Username	Problem	Language	Result	Execution time	Memory
900492		Trisanu_Das	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	328 ms	24144 KiB

cleaning

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
const int N = 200050;

int deg[N];
vector<int> E[N];
const int M = 2 * N;
int root, ls[M], rs[M], sum[M], tsz, lzy[M];

void Flip(int &c, int ss, int se, int qs, int qe) {
    if (qs > qe || qs > se || ss > qe) return;
    if (!c) c = ++tsz;
    if (qs <= ss && qe >= se) {
        sum[c] = se - ss + 1 - sum[c];
        lzy[c] ^= 1;
        return;
    }
    int mid = ss + se >> 1;
    Flip(ls[c], ss, mid, qs, qe);
    Flip(rs[c], mid + 1, se, qs, qe);
    sum[c] = sum[ls[c]] + sum[rs[c]];
    if (lzy[c]) sum[c] = se - ss + 1 - sum[c];
}

int head[N], lid[N], rid[N], tid, sz[N], par[N];

void DFS(int u, int p) {
    sz[u] = 1;
    par[u] = p;
    for (int v : E[u]) if (v != p) DFS(v, u), sz[u] += sz[v];
}

void HLD(int u, int p) {
    lid[u] = ++tid;
    if (!head[u]) head[u] = u;
    int hc = 0;
    for (int v : E[u]) if (v != p && sz[hc] < sz[v]) hc = v;
    if (hc != 0) {
        head[hc] = head[u];
        HLD(hc, u);
        for (int v : E[u]) if (v != p && v != hc) HLD(v, u);
    }
    rid[u] = tid;
}

void Flip(int u) {
    while (u > 0) {
        Flip(root, 2, tid, lid[head[u]], lid[u]);
        u = par[head[u]];
    }
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        E[u].pb(v);
        E[v].pb(u);
        deg[u]++;
        deg[v]++;
    }

    DFS(1, 0);
    HLD(1, 0);

    int leaf = 0;

    for (int i = 1; i <= n; i++) if (deg[i] == 1) Flip(i), leaf++;

    for (int i = 1; i <= q; i++) {
        int k;
        cin >> k;

        vector<int> p(k);
        for (int &j : p) {
            cin >> j;
            deg[j]++;
            if (deg[j] != 2) {
                leaf++;
                Flip(j);
            }
        }

        if (leaf % 2 == 1) cout << "-1\n";
        else cout << n - 1 + k + n - 1 - sum[root] << '\n';

        reverse(p.begin(), p.end());

        for (int j : p) {
            deg[j]--;
            if (deg[j] != 1) {
                leaf--;
                Flip(j);
            }
        }
    }

    return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'void Flip(int&, int, int, int, int)':
cleaning.cpp:22:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = ss + se >> 1;
      |               ~~~^~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30