oj.uz

Submission #830065

# Submission time Handle Problem Language Result Execution time Memory
830065 2023-08-18T18:17:43 Z t6twotwo Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 19632 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int M, leaves, timer;
vector<bool> leaf;
vector<int> f, par, sz, in, top, c0, c1, lz;
vector<vector<int>> adj;
void init(int x) {
    if (adj[x].size() == 1) {
        f[x] = 1;
        leaf[x] = 1;
        leaves ^= 1;
    }
    if (par[x] != -1) {
        adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x]));
    }
    sz[x] = 1;
    for (int &y : adj[x]) {
        par[y] = x;
        init(y);
        f[x] ^= f[y];
        sz[x] += sz[y];
        if (sz[y] > adj[x][0]) {
            swap(y, adj[x][0]);
        }
    }
}
void dfs(int x) {
    in[x] = timer++;
    for (int y : adj[x]) {
        top[y] = adj[x][0] == y ? top[x] : y;
        dfs(y);
    }
}
void apply(int p, int v) {
    if (v == 0) {
        return;
    }
    swap(c0[p], c1[p]);
    lz[p] ^= 1;
}
void push(int p) {
    apply(p * 2, lz[p]);
    apply(p * 2 + 1, lz[p]);
    lz[p] = 0;
}
void pull(int p) {
    c0[p] = c0[p * 2] + c0[p * 2 + 1];
    c1[p] = c1[p * 2] + c1[p * 2 + 1];
}
void upd(int p, int l, int r, int L, int R) {
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply(p, 1);
        return;
    }
    int m = (l + r + 1) / 2;
    push(p);
    upd(p * 2, l, m, L, R);
    upd(p * 2 + 1, m, r, L, R);
    pull(p);
}
void build(vector<int> &a) {
    int N = a.size();
    M = 2 << __lg(N);
    c0.resize(2 * M);
    c1.resize(2 * M);
    lz.resize(2 * M);
    for (int i = 0; i < N; i++) {
        if (a[i] == 0) {
            c0[in[i] + M] = 1;
        } else {
            c1[in[i] + M] = 1;
        }
    }
    for (int i = M - 1; i; i--) {
        pull(i);
    }
}
void update(int s) {
    while (s != -1) {
        upd(1, 0, M, in[top[s]], in[s] + 1);
        s = par[top[s]];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    adj.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f.resize(N);
    in.resize(N);
    sz.resize(N);
    top.resize(N);
    par.resize(N, -1);
    leaf.resize(N);
    init(0);
    dfs(0);
    build(f);
    auto l = leaf;
    while (Q--) {
        int D;
        cin >> D;
        vector<int> p(D);
        for (int i = 0; i < D; i++) {
            cin >> p[i];
            p[i]--;
            if (l[p[i]]) {
                l[p[i]] = 0;
                leaves ^= 1;
            } else {
                update(p[i]);
            }
        }
        leaves ^= D & 1;
        if (leaves == 1) {
            cout << -1 << "\n";
        } else {
            cout << N + D + c0[1] - 2 << "\n";
        }
        leaves ^= D & 1;
        for (int i = 0; i < D; i++) {
            if (leaf[p[i]] && !l[p[i]]) {
                l[p[i]] = 1;
                leaves ^= 1;
            } else {
                update(p[i]);
            }
        }
    }
    return 6/22;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 158 ms 3512 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1352 KB Output is correct
2 Correct 41 ms 1364 KB Output is correct
3 Correct 28 ms 11960 KB Output is correct
4 Correct 56 ms 10236 KB Output is correct
5 Correct 58 ms 12916 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2004 KB Output is correct
2 Correct 33 ms 2004 KB Output is correct
3 Correct 37 ms 19632 KB Output is correct
4 Correct 99 ms 19012 KB Output is correct
5 Correct 29 ms 18128 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 3668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8264 KB Output is correct
2 Correct 207 ms 8064 KB Output is correct
3 Correct 141 ms 4428 KB Output is correct
4 Correct 174 ms 8168 KB Output is correct
5 Correct 188 ms 8184 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 13360 KB Output is correct
2 Execution timed out 1061 ms 15004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 158 ms 3512 KB Output is correct
3 Correct 41 ms 1352 KB Output is correct
4 Correct 41 ms 1364 KB Output is correct
5 Correct 28 ms 11960 KB Output is correct
6 Correct 56 ms 10236 KB Output is correct
7 Correct 58 ms 12916 KB Output is correct
8 Correct 33 ms 2004 KB Output is correct
9 Correct 33 ms 2004 KB Output is correct
10 Correct 37 ms 19632 KB Output is correct
11 Correct 99 ms 19012 KB Output is correct
12 Correct 29 ms 18128 KB Output is correct
13 Execution timed out 1066 ms 3668 KB Time limit exceeded
14 Halted 0 ms 0 KB -