Submission #343648

#	Time	Username	Problem	Language	Result	Execution time	Memory
343648		parsabahrami	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	788 ms	20972 KiB

cleaning

#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 (stderr)

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30