Submission #557275

#	Time	Username	Problem	Language	Result	Execution time	Memory
557275		hoanghq2004	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	514 ms	18988 KiB

cleaning

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int n, q, ans;
vector <int> g[N];
int leaves;
int sz[N], big[N], in[N], head[N], hl[N], par[N], num, ti;

void dfs(int u, int p) {
    sz[u] = 1;
    par[u] = p;
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] >= sz[big[u]]) big[u] = v;
    }
}

void hld(int u, int p) {
    in[u] = ++ti;
    if (big[u]) {
        int v = big[u];
        hl[v] = hl[u];
        head[v] = head[u];
        hld(v, u);
    }
    for (auto v: g[u]) {
        if (v == p || v == big[u]) continue;
        hl[v] = ++num;
        head[v] = v;
        hld(v, u);
    }
}

int vis[N];
int st[N * 4], lazy[N * 4];

void push(int id, int len) {
    lazy[id] ^= 1;
    st[id] = len - st[id];
}

void modify(int id, int L, int R, int u, int v) {
    if (u > R || L > v) return;
    if (u <= L && R <= v) {
        push(id, R - L + 1);
        return;
    }
    int mid = L + R >> 1;
    if (lazy[id]) {
        push(id * 2, mid - L + 1);
        push(id * 2 + 1, R - mid);
        lazy[id] = 0;
    }
    modify(id * 2, L, mid, u, v);
    modify(id * 2 + 1, mid + 1, R, u, v);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void solve() {
    ++ti;
    int m;
    cin >> m;
    vector <int> s, rev;
    int l = leaves + m;
    while (m--) {
        int u;
        cin >> u;
        if (g[u].size() <= 1 && vis[u] != ti) {
            --l;
            vis[u] = ti;
            rev.push_back(u);
        }
        s.push_back(u);
    }
    if (l % 2) {
        cout << -1 << '\n';
        return;
    }
    for (auto u: rev)
        for (; u; u = par[head[u]]) modify(1, 1, n, in[head[u]], in[u]);
    for (auto u: s)
        for (; u; u = par[head[u]]) modify(1, 1, n, in[head[u]], in[u]);
    int _1 = st[1] + s.size();
    int _2 = (n - 1 - st[1]);
    cout << _1 + _2 * 2 << '\n';
    for (auto u: s)
        for (; u; u = par[head[u]]) modify(1, 1, n, in[head[u]], in[u]);
    for (auto u: rev)
        for (; u; u = par[head[u]]) modify(1, 1, n, in[head[u]], in[u]);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int r = 1;
    for (int i = 1; i <= n; ++i)
        if (g[i].size() > 1) r = i;

    dfs(r, 0);
    hl[r] = ++num;
    head[r] = r;
    hld(r, 0);
    for (int i = 1; i <= n; ++i)
        if (g[i].size() <= 1) {
            ++leaves;
            for (int u = i; u; u = par[head[u]]) modify(1, 1, n, in[head[u]], in[u]);
        }
    while (q--) solve();
}

Compilation message (stderr)

cleaning.cpp: In function 'void modify(int, int, int, int, int)':
cleaning.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = L + R >> 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