oj.uz

Submission #924065

# Submission time Handle Problem Language Result Execution time Memory
924065 2024-02-08T11:01:20 Z Camillus Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 150 ms 23632 KB 
/// @author Camillus
#include <bits/stdc++.h>
using namespace std;

static constexpr int maxn = 1 << 17;

vector<int> g[maxn];
int p[maxn];
int sz[maxn];
int cnt[maxn];

int root = 0;

void dfs1(int u) {
    sz[u] = 1;

    auto it = find(g[u].begin(), g[u].end(), p[u]);
    if (it != g[u].end()) g[u].erase(it);

    if (g[u].empty()) {
        cnt[u] = 1;
        return;
    }

    for (int v : g[u]) {
        p[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        cnt[u] += cnt[v];
    }

    int &f = g[u].front();
    for (int &v : g[u]) {
        if (sz[v] > sz[f]) {
            swap(f, v);
        }
    }
}


int tin[maxn];
int head[maxn];
int timer = 0;

void dfs2(int u) {
    tin[u] = timer++;

    if (head[u] == 0) {
        head[u] = u;
    }

    if (!g[u].empty()) {
        head[g[u].front()] = head[u];
    }

    for (int v : g[u]) {
        dfs2(v);
    }
}

namespace st {
    using value_t = array<int, 2>;
    value_t cnt[maxn * 2 - 1];
    bool reversed[maxn * 2 - 1];

    constexpr value_t merge(const value_t &first, const value_t &second) {
        return {first[0] + second[0], first[1] + second[1]};
    }

    inline void apply(int x) {
        swap(cnt[x][0], cnt[x][1]);
        reversed[x] ^= 1;
    }

    inline void push(int x) {
        if (reversed[x]) {
            apply(x * 2 + 1);
            apply(x * 2 + 2);
            reversed[x] = false;
        }
    }

    void reverse(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x);
            return;
        }

        push(x);

        reverse(l, r, x * 2 + 1, lx, (lx + rx) / 2);
        reverse(l, r, x * 2 + 2, (lx + rx) / 2, rx);

        cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
    }

    value_t get(int i, int x = 0, int lx = 0, int rx = maxn) {
        if (rx - lx == 1) {
            return cnt[x];
        }

        push(x);

        if (i < (lx + rx) / 2) {
            return get(i, x * 2 + 1, lx, (lx + rx) / 2);
        } else {
            return get(i, x * 2 + 2, (lx + rx) / 2, rx);
        }
    }

    void build(int n) {
        for (int u = 1; u <= n; u++) {
            int x = maxn + tin[u] - 1;
            cnt[x][::cnt[u] % 2] = 1;
        }

        for (int x = maxn - 2; x >= 0; x--) {
            cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
        }
    }
} // namespace st

void reverse_path(int u) {
    while (true) {
        int v = head[u];

        st::reverse(tin[v], tin[u] + 1);

        u = v;

        if (u == root) {
            break;
        } else {
            u = p[u];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int u = 1; u <= n; u++) {
        if (g[u].size() > 1) {
            root = u;
        }
    }

    dfs1(root);
    dfs2(root);

    st::build(n);

    while (q--) {
        int d;
        cin >> d;

        map<int, int> c;

        for (int i = 0; i < d; i++) {
            int u;
            cin >> u;

            c[u] ^= 1;
        }

        for (auto &[u, k] : c) {
            if (g[u].size() == 0) {
                k ^= 1;
            }
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }

        auto result = st::cnt[0];

        result[1] += d;

        if (st::get(0)[1]) {
            cout << -1 << '\n';
        } else {
            cout << (result[0] - 1) * 2 + result[1] << '\n';
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 83 ms 7236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6488 KB Output is correct
2 Correct 13 ms 6744 KB Output is correct
3 Correct 21 ms 12232 KB Output is correct
4 Correct 51 ms 13260 KB Output is correct
5 Correct 73 ms 15360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7000 KB Output is correct
2 Correct 14 ms 7516 KB Output is correct
3 Correct 44 ms 21348 KB Output is correct
4 Correct 75 ms 23204 KB Output is correct
5 Correct 50 ms 19948 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8128 KB Output is correct
2 Correct 34 ms 7516 KB Output is correct
3 Correct 8 ms 7256 KB Output is correct
4 Correct 8 ms 7772 KB Output is correct
5 Correct 9 ms 7772 KB Output is correct
6 Correct 42 ms 8284 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9684 KB Output is correct
2 Correct 149 ms 9308 KB Output is correct
3 Correct 125 ms 8688 KB Output is correct
4 Correct 148 ms 10656 KB Output is correct
5 Correct 150 ms 10696 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11508 KB Output is correct
2 Correct 75 ms 16720 KB Output is correct
3 Correct 107 ms 15964 KB Output is correct
4 Correct 113 ms 16500 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 83 ms 7236 KB Output is correct
3 Correct 13 ms 6488 KB Output is correct
4 Correct 13 ms 6744 KB Output is correct
5 Correct 21 ms 12232 KB Output is correct
6 Correct 51 ms 13260 KB Output is correct
7 Correct 73 ms 15360 KB Output is correct
8 Correct 14 ms 7000 KB Output is correct
9 Correct 14 ms 7516 KB Output is correct
10 Correct 44 ms 21348 KB Output is correct
11 Correct 75 ms 23204 KB Output is correct
12 Correct 50 ms 19948 KB Output is correct
13 Correct 44 ms 8128 KB Output is correct
14 Correct 34 ms 7516 KB Output is correct
15 Correct 8 ms 7256 KB Output is correct
16 Correct 8 ms 7772 KB Output is correct
17 Correct 9 ms 7772 KB Output is correct
18 Correct 42 ms 8284 KB Output is correct
19 Correct 104 ms 9684 KB Output is correct
20 Correct 149 ms 9308 KB Output is correct
21 Correct 125 ms 8688 KB Output is correct
22 Correct 148 ms 10656 KB Output is correct
23 Correct 150 ms 10696 KB Output is correct
24 Correct 131 ms 11508 KB Output is correct
25 Correct 75 ms 16720 KB Output is correct
26 Correct 107 ms 15964 KB Output is correct
27 Correct 113 ms 16500 KB Output is correct
28 Correct 113 ms 10648 KB Output is correct
29 Correct 76 ms 15740 KB Output is correct
30 Correct 61 ms 15368 KB Output is correct
31 Correct 80 ms 23632 KB Output is correct
32 Correct 147 ms 10836 KB Output is correct
33 Correct 94 ms 15440 KB Output is correct
34 Correct 113 ms 15492 KB Output is correct
35 Correct 109 ms 16512 KB Output is correct