제출 #546035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546035		tengiz05	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	307 ms	20912 KiB

cleaning

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

struct SegmentTree {
    int n;
    vector<int> t, lz;
    SegmentTree(int n) : n(n), t(4 * n), lz(4 * n) {}
    void push(int p, int len) {
        if (!lz[p])
            return;
        t[p] = len - t[p];
        if (len > 1) {
            lz[2 * p] ^= 1;
            lz[2 * p + 1] ^= 1;
        }
        lz[p] = 0;
    }
    void update(int p, int l, int r, int x, int y) {
        push(p, r - l);
        if (r <= x || y <= l) {
            return;
        }
        if (x <= l && r <= y) {
            lz[p] = 1;
            push(p, r - l);
            return;
        }
        int m = (l + r) / 2;
        update(2 * p, l, m, x, y);
        update(2 * p + 1, m, r, x, y);
        t[p] = t[2 * p] + t[2 * p + 1];
    }
    void update(int l, int r) {
        update(1, 0, n, l, r);
    }
    int get(int p, int l, int r, int x) {
        push(p, r - l);
        if (l == r - 1) {
            return t[p];
        }
        int m = (l + r) / 2;
        if (x < m) {
            return get(2 * p, l, m, x);
        } else {
            return get(2 * p + 1, m, r, x);
        }
    }
    int get(int x) {
        return get(1, 0, n, x);
    }
};

constexpr int N = 1E5;

vector<int> e[N];
int deg[N];

int par[N], c[N], siz[N], h[N], in[N], out[N];
void dfs(int u, int p) {
    h[u] = -1;
    siz[u] = 1;
    c[u] = e[u].size() == 1;
    par[u] = p;
    if (p != -1)
        e[u].erase(find(e[u].begin(), e[u].end(), p));
    for (int &v : e[u]) {
        dfs(v, u);
        c[u] ^= c[v];
        siz[u] += siz[v];
        if (siz[e[u][0]] < siz[v]) {
            swap(e[u][0], v);
        }
    }
}
int timeStamp = 0;
int nxt[N];
void dfs2(int u) {
    in[u] = timeStamp++;
    for (int v : e[u]) {
        nxt[v] = (v == e[u][0] ? nxt[u] : v);
        dfs2(v);
    }
    out[u] = timeStamp;
}
SegmentTree s(N);
void update(int u) {
    while (u != -1) {
        s.update(in[nxt[u]], in[u] + 1);
        u = par[nxt[u]];
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, nQ;
    cin >> n >> nQ;
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    
    int r = -1;
    for (int i = 0; i < n; i++) {
        if (deg[i] > 1) {
            r = i;
        }
    }
    
    dfs(r, -1);
    nxt[r] = r;
    dfs2(r);
    for (int i = 0; i < n; i++)
        if (c[i])
            s.update(in[i], in[i] + 1);
    
    while (nQ--) {
        int k;
        cin >> k;
        
        vector<int> v(k);
        for (int i = 0; i < k; i++) {
            cin >> v[i];
            v[i]--;
        }
        
        for (int x : v) {
            deg[x]++;
            if (deg[x] == 2)
                continue;
            update(x);
        }
        
        int cnt = n - s.t[1];
        
        if (s.get(in[r]) == 0) {
            cout << n + k + cnt - 2 << "\n";
        } else {
            cout << "-1\n";
        }
        
        for (int x : v) {
            deg[x]--;
            if (deg[x] == 1)
                continue;
            update(x);
        }
    }
    
    return 0;
}

• 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