oj.uz

Submission #578163

# Submission time Handle Problem Language Result Execution time Memory
578163 2022-06-16T06:32:22 Z tengiz05 Spring cleaning (CEOI20_cleaning) C++17
35 / 100
 159 ms 23316 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

struct SegmentTree {
    int n;
    vector<int> t;
    SegmentTree(int n) : n(n), t(2 * n) {}
    int get(int l, int r) {
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                res ^= t[l++];
            if (r & 1)
                res ^= t[--r];
        }
        return res;
    }
    void update(int x) {
        for (x += n; x > 0; x >>= 1) {
            t[x] ^= 1;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<vector<int>> e(n);
    
    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);
    }
    
    vector<int> c(n), in(n), out(n);
    vector s(2, vector<int>(n));
    
    int timeStamp = 0;
    int cnt = 0;
    
    function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = timeStamp++;
        c[u] = e[u].size() <= 1;
        cnt += c[u];
        for (int v : e[u]) {
            if (v != p) {
                dfs(v, u);
                c[u] ^= c[v];
            }
        }
        out[u] = timeStamp;
    };
    
    dfs(0, -1);
    
    int f[2] {};
    
    dfs = [&](int u, int p) {
        if (p != -1) {
            s[1][u] += c[u];
            s[0][u] += !c[u];
            f[c[u]]++;
        }
        for (int v : e[u]) {
            if (v != p) {
                s[1][v] = s[1][u];
                s[0][v] = s[0][u];
                dfs(v, u);
            }
        }
    };
    
    dfs(0, -1);
    
    SegmentTree t(n);
    
    while (q--) {
        int k;
        cin >> k;
        
        vector<int> d(k);
        for (int i = 0; i < k; i++) {
            cin >> d[i];
            d[i]--;
        }
        
        set<int> v(d.begin(), d.end());
        int leaves = cnt + k;
        for (int x : v) {
            if (e[x].size() <= 1) {
                leaves--;
            }
        }
        
        if (leaves % 2 != 0) {
            cout << "-1\n";
            continue;
        }
        
        int a[2] {f[0], f[1]};
        
        set<int> done;
        
        sort(d.begin(), d.end(), [&](int i, int j) {
            return in[i] > in[j];
        });
        for (int u : d) {
            if (e[u].size() <= 1 && !done.count(u)) {
                // nothing?
            } else {
                int x = t.get(in[u], out[u]);
                a[1] -= s[1 ^ x][u];
                a[1] += s[0 ^ x][u];
                a[0] -= s[0 ^ x][u];
                a[0] += s[1 ^ x][u];
                t.update(in[u]);
            }
            done.insert(u);
        }
        int ans = 2 * a[0] + a[1] + k;
        cout << ans << "\n";
        done.clear();
        for (int u : d) {
            if (e[u].size() <= 1 && !done.count(u)) {
                // nothing?
            } else {
                int x = t.get(in[u], out[u]);
                t.update(in[u]);
            }
            done.insert(u);
        }
    }
    
    return 0;
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:137:21: warning: unused variable 'x' [-Wunused-variable]
  137 |                 int x = t.get(in[u], out[u]);
      |                     ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 63 ms 2376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1144 KB Output is correct
2 Correct 11 ms 980 KB Output is correct
3 Correct 39 ms 9304 KB Output is correct
4 Correct 101 ms 11412 KB Output is correct
5 Correct 159 ms 14848 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1944 KB Output is correct
2 Correct 13 ms 1748 KB Output is correct
3 Correct 55 ms 19432 KB Output is correct
4 Correct 124 ms 23316 KB Output is correct
5 Correct 73 ms 17564 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5952 KB Output is correct
2 Incorrect 100 ms 5972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 9076 KB Output is correct
2 Correct 136 ms 12940 KB Output is correct
3 Correct 104 ms 11972 KB Output is correct
4 Correct 111 ms 13656 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 63 ms 2376 KB Output isn't correct
3 Halted 0 ms 0 KB -