Submission #342463

#	Time	Username	Problem	Language	Result	Execution time	Memory
342463		mjhmjh1104	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	883 ms	27612 KiB

cleaning

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 100006;

long long tree1[262144]; /// mod 2
long long lazy1[262144];

void propagate1(int i, int b, int e) {
    if (!lazy1[i]) return;
    if (b != e) {
        lazy1[i * 2 + 1] += lazy1[i];
        lazy1[i * 2 + 2] += lazy1[i];
    }
    if (lazy1[i] % 2) tree1[i] = (e - b + 1) - tree1[i];
    lazy1[i] = 0;
}

long long update1(int i, int b, int e, int l, int r, int v) {
    propagate1(i, b, e);
    if (r < b || e < l) return tree1[i];
    if (l <= b && e <= r) {
        lazy1[i] += v;
        propagate1(i, b, e);
        return tree1[i];
    }
    int m = (b + e) / 2;
    return tree1[i] = update1(i * 2 + 1, b, m, l, r, v) + update1(i * 2 + 2, m + 1, e, l, r, v);
}

long long tree2[262144]; /// more than 0
long long lazy2[262144];

void update2(int i, int b, int e, int l, int r, int v) {
    if (r < b || e < l) return;
    int m = (b + e) / 2;
    if (l <= b && e <= r) lazy2[i] += v;
    else update2(i * 2 + 1, b, m, l, r, v), update2(i * 2 + 2, m + 1, e, l, r, v);
    if (lazy2[i]) tree2[i] = e - b + 1;
    else if (b == e) tree2[i] = 0;
    else tree2[i] = tree2[i * 2 + 1] + tree2[i * 2 + 2];
}

void update(int l, int r, int v) {
    update1(0, 0, 131071, l, r, v);
    update2(0, 0, 131071, l, r, v);
}

int sz[MAX], in[MAX], top[MAX], t;
int n, q, d, childs[MAX], depth[MAX], par[MAX];
bool alreadyLeaf[MAX];
vector<int> adj[MAX], c[MAX];

int dfs_sz(int x) {
    sz[x] = 1;
    for (auto &i: c[x]) {
        sz[x] += dfs_sz(i);
        if (sz[i] > sz[c[x][0]]) swap(i, c[x][0]);
    }
    return sz[x];
}

void dfs_hld(int x) {
    in[x] = t++;
    for (auto &i: c[x]) {
        top[i] = (i == c[x][0] ? top[x] : i);
        dfs_hld(i);
    }
}


void dfs(int x, int prev = -1) {
    par[x] = prev;
    for (auto &i: adj[x]) if (i != prev) {
        depth[i] = depth[x] + 1;
        dfs(i, x);
        c[x].push_back(i);
    }
}

void update_hld(int x, int y, int v) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) swap(x, y);
        update(in[top[x]], in[x], v);
        x = par[top[x]];
    }
    if (in[x] > in[y]) swap(x, y);
    update(in[x], in[y], v);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0);
    dfs_sz(0);
    dfs_hld(0);
    int r = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 && (int)c[0].size() != 1) continue;
        if (i != 0 && !c[i].empty()) continue;
        update_hld(0, i, 1);
        alreadyLeaf[i] = true;
        r++;
    }
    int _or = r;
    while (q--) {
        r = _or;
        scanf("%d", &d);
        vector<int> x;
        for (int i = 0; i < d; i++) {
            int t;
            scanf("%d", &t); t--;
            x.push_back(t);
            childs[t]++;
            if (alreadyLeaf[t] && childs[t] == 1) continue;
            update_hld(0, t, 1), r++;
        }
        if (r % 2) {
            puts("-1");
            goto next;
        }
        {
            propagate1(0, 0, 131071);
            long long first = tree1[0];
            long long second = tree2[0];
            if (r > 0) second--;
            printf("%lld\n", 2 * second - first + d);
        }

    next:
        for (int i = (int)x.size() - 1; i >= 0; i--) {
            childs[x[i]]--;
            if (alreadyLeaf[x[i]] && !childs[x[i]]) continue;
            update_hld(0, x[i], -1);
        }
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%d", &d);
      |         ~~~~~^~~~~~~~~~
cleaning.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |             scanf("%d", &t); t--;
      |             ~~~~~^~~~~~~~~~

• 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