oj.uz

Submission #343648

# Submission time Handle Problem Language Result Execution time Memory
343648 2021-01-04T10:30:51 Z parsabahrami Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 788 ms 20972 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 1e5 + 10;
int leaf[N], A[N], seg[N << 2], lz[N << 2], St[N], M[N], H[N], S[N], HD[N], P[N], C[N], n, q, tim, rt;
vector<int> adj[N];

void shift(int id, int l, int r) {
    if (!lz[id]) return;
    seg[id] = r - l - seg[id];
    if (r - l > 1) {
        lz[lc] ^= 1, lz[rc] ^= 1;
    }
    lz[id] = 0;
}

void update(int ql, int qr, int x, int id = 1, int l = 0, int r = tim) {
    shift(id, l, r);
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) {
        lz[id] ^= x;
        return shift(id, l, r);
    }
    int mid = (l + r) >> 1;
    update(ql, qr, x, lc, l, mid);
    update(ql, qr, x, rc, mid, r);
    seg[id] = seg[lc] + seg[rc];
}

void preDFS(int v, int p = -1) {
    P[v] = p, C[v] = (SZ(adj[v]) == 1), S[v] = 1;
    for (int u : adj[v]) {
        if (u != p) H[u] = H[v] + 1, preDFS(u, v), S[v] += S[u], C[v] += C[u];
    }
    for (int u : adj[v]) if (S[M[v]] < S[u] && u != p) M[v] = u;
}

void HLD(int v, int p = -1) {
    if (p == -1) HD[v] = v;
    St[v] = tim++;
    if (M[v]) HD[M[v]] = HD[v], HLD(M[v], v);
    for (int u : adj[v]) {
        if (u != M[v] && u != p) HD[u] = u, HLD(u, v);
    }
}

int get(int id = 1, int l = 0, int r = tim) {
    shift(id, l, r);
    if (r - l == 1) return seg[id];
    int mid = (l + r) >> 1;

    return get(lc, l, mid);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (SZ(adj[i]) > 1) rt = i;
    preDFS(rt);
    HLD(rt);
    for (int i = 1; i <= n; i++) {
        update(St[i], St[i] + 1, !(C[i] & 1));
    }
    for (; q; q--) {
        int k; scanf("%d", &k);
        for (int i = 1; i <= k; i++) {
            scanf("%d", &A[i]);
            int v = A[i];
            if (SZ(adj[v]) == 1 && !leaf[v]) {
                leaf[v] = 1;
                int u = v;
                while (~u) {
                    update(St[HD[u]], St[u] + 1, 1);
                    u = P[HD[u]];
                }
            }
            while (~v) {
                update(St[HD[v]], St[v] + 1, 1);
                v = P[HD[v]];
            }
        }
        int t = get();
        if (!(t & 1)) printf("-1\n");
        else printf("%d\n", n + k + seg[1] - 2);
        for (int i = 1; i <= k; i++) {
            if (leaf[A[i]]) {
                int u = A[i];
                while (~u) {
                    update(St[HD[u]], St[u] + 1, 1);
                    u = P[HD[u]];
                }
                leaf[A[i]] = 0;
            }
            int v = A[i];
            while (~v) {
                update(St[HD[v]], St[v] + 1, 1);
                v = P[HD[v]];
            }
        }
    }
    return 0;
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:68:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:79:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         int k; scanf("%d", &k);
      |                ~~~~~^~~~~~~~~~
cleaning.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |             scanf("%d", &A[i]);
      |             ~~~~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 352 ms 5228 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3692 KB Output is correct
2 Correct 69 ms 3692 KB Output is correct
3 Correct 93 ms 11620 KB Output is correct
4 Correct 241 ms 10340 KB Output is correct
5 Correct 277 ms 12388 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4332 KB Output is correct
2 Correct 62 ms 4332 KB Output is correct
3 Correct 96 ms 20972 KB Output is correct
4 Correct 193 ms 20588 KB Output is correct
5 Correct 98 ms 19052 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 5740 KB Output is correct
2 Correct 132 ms 4844 KB Output is correct
3 Correct 19 ms 4716 KB Output is correct
4 Correct 19 ms 5228 KB Output is correct
5 Correct 28 ms 5228 KB Output is correct
6 Correct 114 ms 5740 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 9344 KB Output is correct
2 Correct 753 ms 9196 KB Output is correct
3 Correct 635 ms 6380 KB Output is correct
4 Correct 784 ms 9264 KB Output is correct
5 Correct 788 ms 9324 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 13548 KB Output is correct
2 Correct 338 ms 16876 KB Output is correct
3 Correct 372 ms 16108 KB Output is correct
4 Correct 331 ms 16748 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 352 ms 5228 KB Output is correct
3 Correct 71 ms 3692 KB Output is correct
4 Correct 69 ms 3692 KB Output is correct
5 Correct 93 ms 11620 KB Output is correct
6 Correct 241 ms 10340 KB Output is correct
7 Correct 277 ms 12388 KB Output is correct
8 Correct 61 ms 4332 KB Output is correct
9 Correct 62 ms 4332 KB Output is correct
10 Correct 96 ms 20972 KB Output is correct
11 Correct 193 ms 20588 KB Output is correct
12 Correct 98 ms 19052 KB Output is correct
13 Correct 174 ms 5740 KB Output is correct
14 Correct 132 ms 4844 KB Output is correct
15 Correct 19 ms 4716 KB Output is correct
16 Correct 19 ms 5228 KB Output is correct
17 Correct 28 ms 5228 KB Output is correct
18 Correct 114 ms 5740 KB Output is correct
19 Correct 493 ms 9344 KB Output is correct
20 Correct 753 ms 9196 KB Output is correct
21 Correct 635 ms 6380 KB Output is correct
22 Correct 784 ms 9264 KB Output is correct
23 Correct 788 ms 9324 KB Output is correct
24 Correct 645 ms 13548 KB Output is correct
25 Correct 338 ms 16876 KB Output is correct
26 Correct 372 ms 16108 KB Output is correct
27 Correct 331 ms 16748 KB Output is correct
28 Correct 508 ms 9028 KB Output is correct
29 Correct 319 ms 15724 KB Output is correct
30 Correct 268 ms 12388 KB Output is correct
31 Correct 200 ms 20576 KB Output is correct
32 Correct 765 ms 9196 KB Output is correct
33 Correct 344 ms 15212 KB Output is correct
34 Correct 384 ms 15468 KB Output is correct
35 Correct 384 ms 16492 KB Output is correct