Submission #1167012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167012		aycnl	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	168 ms	17796 KiB

cleaning

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

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(998244353)
#define maxN 100005

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

int n, q, tme, root;
vi ke[maxN];
int sz[maxN], h[maxN], par[maxN], mark[maxN];
int top[maxN], pos[maxN];
int st[4*maxN], lazy[4*maxN];
int t[maxN];

void down(int id, int l, int r) {
    lazy[id] = 0;
    lazy[id*2] ^= 1;
    lazy[id*2+1] ^= 1;
    int m = (l+r)/2;
    st[id*2] = (m-l+1) - st[id*2];
    st[id*2+1] = (r-m) - st[id*2+1];
}

void ud(int id, int l, int r, int i, int j) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        st[id] = (r-l+1) - st[id];
        lazy[id] ^= 1;
        return;
    }
    if (lazy[id]) down(id, l, r);
    int m = (l+r)/2;
    ud(id*2, l, m, i, j);
    ud(id*2+1, m+1, r, i, j);
    st[id] = st[id*2] + st[id*2+1];
}

void pre_dfs(int u) {
    sz[u] = 1;
    for (int v : ke[u]) if (v != par[u]) {
        par[v] = u;
        h[v] = h[u] + 1;
        pre_dfs(v);
        sz[u] += sz[v];
    }
}

void hld(int u, int tp) {
    top[u] = tp;
    pos[u] = tme++;

    int bigC = 0;
    for (int v : ke[u]) if (v != par[u]) {
        if (sz[v] > sz[bigC]) bigC = v;
    }
    //cout << u << " " << bigC << endl;

    if (bigC) hld(bigC, tp);
    for (int v : ke[u]) if (v != par[u]) {
        if (v != bigC) hld(v, v);
    }
}

void treeud(int u) {
    while (1) {
        if (top[u] == root) {
            if (u != root) ud(1, 1, n-1, 1, pos[u]);
            break;
        }
        ud(1, 1, n-1, pos[top[u]], pos[u]);
        //ud(1, 1, n-1, pos[top[u]], pos[top[u]]);
        u = par[top[u]];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    fto(i, 1, n-1) {
        int u, v; cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    fto(i, 1, n) if (ke[i].size() != 1) {
        root = i;
        break;
    }
    //cout << root << endl;
    pre_dfs(root);
    hld(root, root);
    //return 0;

    int cr = 0;
    fto(i, 1, n) if (int(ke[i].size()) == 1) {
        ++cr;
        treeud(i);
    }
    //cout << st[1] << endl;

    while (q--) {
        int d; cin >> d;
        unordered_map<int, int> mp;
        int cur = cr;
        fto(i, 1, d) cin >> t[i];

        fto(i, 1, d) {
            cur++;
            if (ke[t[i]].size() > 1 || mp.count(t[i])) treeud(t[i]);
            else --cur;
            mp[t[i]] = 1;
        }

        //cout << cur << endl;
        if (cur%2 == 0) cout << 2*n - 2 - st[1] + d << endl;
        else cout << -1 << endl;

        mp.clear();
        fto(i, 1, d) {
            if (ke[t[i]].size() > 1 || mp.count(t[i])) treeud(t[i]);
            mp[t[i]] = 1;
        }
    }

    return 0;
}

• 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