oj.uz

Submission #546035

# Submission time Handle Problem Language Result Execution time Memory
546035 2022-04-06T05:25:31 Z tengiz05 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 307 ms 20912 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 126 ms 7880 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6728 KB Output is correct
2 Correct 90 ms 6740 KB Output is correct
3 Correct 65 ms 13284 KB Output is correct
4 Correct 82 ms 11888 KB Output is correct
5 Correct 89 ms 13976 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7276 KB Output is correct
2 Correct 62 ms 7252 KB Output is correct
3 Correct 93 ms 20912 KB Output is correct
4 Correct 133 ms 20300 KB Output is correct
5 Correct 62 ms 19488 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 8212 KB Output is correct
2 Correct 69 ms 7496 KB Output is correct
3 Correct 14 ms 7264 KB Output is correct
4 Correct 15 ms 7844 KB Output is correct
5 Correct 18 ms 7764 KB Output is correct
6 Correct 61 ms 8196 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 11396 KB Output is correct
2 Correct 307 ms 11220 KB Output is correct
3 Correct 246 ms 8776 KB Output is correct
4 Correct 249 ms 11300 KB Output is correct
5 Correct 229 ms 11400 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 14664 KB Output is correct
2 Correct 131 ms 17356 KB Output is correct
3 Correct 208 ms 16756 KB Output is correct
4 Correct 171 ms 17208 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 126 ms 7880 KB Output is correct
3 Correct 76 ms 6728 KB Output is correct
4 Correct 90 ms 6740 KB Output is correct
5 Correct 65 ms 13284 KB Output is correct
6 Correct 82 ms 11888 KB Output is correct
7 Correct 89 ms 13976 KB Output is correct
8 Correct 63 ms 7276 KB Output is correct
9 Correct 62 ms 7252 KB Output is correct
10 Correct 93 ms 20912 KB Output is correct
11 Correct 133 ms 20300 KB Output is correct
12 Correct 62 ms 19488 KB Output is correct
13 Correct 108 ms 8212 KB Output is correct
14 Correct 69 ms 7496 KB Output is correct
15 Correct 14 ms 7264 KB Output is correct
16 Correct 15 ms 7844 KB Output is correct
17 Correct 18 ms 7764 KB Output is correct
18 Correct 61 ms 8196 KB Output is correct
19 Correct 197 ms 11396 KB Output is correct
20 Correct 307 ms 11220 KB Output is correct
21 Correct 246 ms 8776 KB Output is correct
22 Correct 249 ms 11300 KB Output is correct
23 Correct 229 ms 11400 KB Output is correct
24 Correct 278 ms 14664 KB Output is correct
25 Correct 131 ms 17356 KB Output is correct
26 Correct 208 ms 16756 KB Output is correct
27 Correct 171 ms 17208 KB Output is correct
28 Correct 178 ms 10972 KB Output is correct
29 Correct 201 ms 16200 KB Output is correct
30 Correct 92 ms 13976 KB Output is correct
31 Correct 134 ms 20396 KB Output is correct
32 Correct 270 ms 11332 KB Output is correct
33 Correct 151 ms 15552 KB Output is correct
34 Correct 185 ms 15908 KB Output is correct
35 Correct 204 ms 16856 KB Output is correct