oj.uz

Submission #574667

# Submission time Handle Problem Language Result Execution time Memory
574667 2022-06-09T07:17:38 Z piOOE Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 171 ms 21964 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 200000, infI = 1e9 + 7;
const ll infL = 3e18;

vector<int> g[N];

int cnt[N], tin[N], rev[N], head[N], sz[N], parent[N], T = 0;

void dfs1(int v, int p) {
    sz[v] = 1;
    int mx = -1;
    for (int i = 0; i < sz(g[v]); ++i) {
        int to = g[v][i];
        if (to != p) {
            dfs1(to, v);
            sz[v] += sz[to];
            if (mx == -1 || sz[g[v][mx]] < sz[to]) {
                mx = i;
            }
        }
    }
    if (mx != -1) {
        swap(g[v][0], g[v][mx]);
    }
}

void dfs2(int v, int p, int pp) {
    if (pp == -1) {
        head[v] = v;
    } else {
        head[v] = pp;
    }
    tin[v] = T++;
    parent[v] = p;
    rev[tin[v]] = v;
    if (sz(g[v]) <= 1) {
        cnt[v] = 1;
    } else {
        cnt[v] = 0;
        dfs2(g[v][0], v, head[v]);
        for (int i = 1; i < sz(g[v]); ++i) {
            if (g[v][i] != p) {
                dfs2(g[v][i], v, -1);
            }
        }
        for (int to: g[v]) {
            if (to != p) {
                cnt[v] ^= cnt[to];
            }
        }
    }
}

struct node {
    int cnt[2] = {0, 0};

    node() = default;
};

node operator+(node a, node b) {
    return {a.cnt[0] + b.cnt[0], a.cnt[1] + b.cnt[1]};
}

vector<node> t;
vector<int> xored;
int siz = 1;

void init(int n) {
    siz = 1;
    while (siz < n) {
        siz <<= 1;
    }
    t.assign(siz << 1, {});
    xored.assign(siz << 1, 0);
    for (int i = 0; i < n; ++i) {
        ++t[i + siz].cnt[cnt[rev[i]]];
    }
    for (int i = siz - 1; i > 0; --i) {
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

void modify(int l, int r, int x = 1, int lx = 0, int rx = siz) {
    if (l >= rx || lx >= r) {
        return;
    }
    if (l <= lx && rx <= r) {
        xored[x] ^= 1;
        swap(t[x].cnt[0], t[x].cnt[1]);
        return;
    }
    int m = (lx + rx) >> 1;
    modify(l, r, x << 1, lx, m), modify(l, r, x << 1 | 1, m, rx);
    t[x] = t[x << 1] + t[x << 1 | 1];
    if (xored[x]) {
        swap(t[x].cnt[0], t[x].cnt[1]);
    }
}

void xor_path(int v) {
    while (v != -1) {
        modify(tin[head[v]], tin[v] + 1);
        v = parent[head[v]];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    int root = -1;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < n; ++i) {
        if (sz(g[i]) > 1) {
            root = i;
            break;
        }
    }
    assert(root != -1);
    dfs1(root, -1);
    dfs2(root, -1, -1);
    init(n);
    int leaves = cnt[root];
    while (q--) {
        int D;
        cin >> D;
        vector<int> a(D);
        for (int i = 0; i < D; ++i) {
            cin >> a[i];
            --a[i];
        }
        sort(all(a));
        for (int i = 0; i < D;) {
            int j = i;
            while (j < D && a[j] == a[i]) {
                ++j;
            }
            if (sz(g[a[i]]) > 1) {
                if ((j - i) % 2 == 1) {
                    xor_path(a[i]);
                }
                leaves ^= ((j - i) & 1);
            } else {
                if (j > i + 1) {
                    if ((j - i) % 2 == 0) {
                        xor_path(a[i]);
                        leaves ^= 1;
                    }
                }
            }
            i = j;
        }
        if (leaves) {
            cout << "-1\n";
        } else {
            cout << D + t[1].cnt[0] * 2 + t[1].cnt[1] * 1 - 2 << '\n';
        }
        for (int i = 0; i < D;) {
            int j = i;
            while (j < D && a[j] == a[i]) {
                ++j;
            }
            if (sz(g[a[i]]) > 1) {
                if ((j - i) % 2 == 1) {
                    xor_path(a[i]);
                }
                leaves ^= ((j - i) & 1);
            } else {
                if (j > i + 1) {
                    if ((j - i) % 2 == 0) {
                        xor_path(a[i]);
                        leaves ^= 1;
                    }
                }
            }
            i = j;
        }
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 86 ms 7372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5844 KB Output is correct
2 Correct 17 ms 5972 KB Output is correct
3 Correct 32 ms 14792 KB Output is correct
4 Correct 57 ms 13616 KB Output is correct
5 Correct 65 ms 15616 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6432 KB Output is correct
2 Correct 18 ms 6448 KB Output is correct
3 Correct 59 ms 21452 KB Output is correct
4 Correct 85 ms 20652 KB Output is correct
5 Correct 44 ms 20188 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7872 KB Output is correct
2 Correct 35 ms 7244 KB Output is correct
3 Correct 13 ms 7124 KB Output is correct
4 Correct 13 ms 7764 KB Output is correct
5 Correct 15 ms 7804 KB Output is correct
6 Correct 59 ms 7956 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10608 KB Output is correct
2 Correct 168 ms 10404 KB Output is correct
3 Correct 143 ms 8580 KB Output is correct
4 Correct 164 ms 11480 KB Output is correct
5 Correct 165 ms 11456 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 14636 KB Output is correct
2 Correct 118 ms 17244 KB Output is correct
3 Correct 163 ms 17376 KB Output is correct
4 Correct 132 ms 16792 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 86 ms 7372 KB Output is correct
3 Correct 16 ms 5844 KB Output is correct
4 Correct 17 ms 5972 KB Output is correct
5 Correct 32 ms 14792 KB Output is correct
6 Correct 57 ms 13616 KB Output is correct
7 Correct 65 ms 15616 KB Output is correct
8 Correct 22 ms 6432 KB Output is correct
9 Correct 18 ms 6448 KB Output is correct
10 Correct 59 ms 21452 KB Output is correct
11 Correct 85 ms 20652 KB Output is correct
12 Correct 44 ms 20188 KB Output is correct
13 Correct 51 ms 7872 KB Output is correct
14 Correct 35 ms 7244 KB Output is correct
15 Correct 13 ms 7124 KB Output is correct
16 Correct 13 ms 7764 KB Output is correct
17 Correct 15 ms 7804 KB Output is correct
18 Correct 59 ms 7956 KB Output is correct
19 Correct 110 ms 10608 KB Output is correct
20 Correct 168 ms 10404 KB Output is correct
21 Correct 143 ms 8580 KB Output is correct
22 Correct 164 ms 11480 KB Output is correct
23 Correct 165 ms 11456 KB Output is correct
24 Correct 161 ms 14636 KB Output is correct
25 Correct 118 ms 17244 KB Output is correct
26 Correct 163 ms 17376 KB Output is correct
27 Correct 132 ms 16792 KB Output is correct
28 Correct 147 ms 11180 KB Output is correct
29 Correct 102 ms 18612 KB Output is correct
30 Correct 60 ms 15580 KB Output is correct
31 Correct 73 ms 21964 KB Output is correct
32 Correct 171 ms 11552 KB Output is correct
33 Correct 156 ms 16472 KB Output is correct
34 Correct 135 ms 18520 KB Output is correct
35 Correct 148 ms 18384 KB Output is correct