oj.uz

Submission #578137

# Submission time Handle Problem Language Result Execution time Memory
578137 2022-06-16T05:37:25 Z tengiz05 Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 21336 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

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);
    }
    
    while (q--) {
        int k;
        cin >> k;
        
        vector<int> d(k);
        for (int i = 0; i < k; i++) {
            cin >> d[i];
            d[i]--;
        }
        
        auto adj = e;
        adj.resize(n + k);
        for (int i = 0; i < k; i++) {
            adj[d[i]].push_back(i + n);
        }
        
        int ans = 0;
        
        function<int(int, int)> dfs = [&](int u, int p) {
            int c = adj[u].size() <= 1;
            for (int v : adj[u]) {
                if (v != p) {
                    int s = dfs(v, u);
                    if (s % 2 == 0) {
                        ans += 2;
                    } else {
                        ans += 1;
                    }
                    c += s;
                }
            }
            return c;
        };
        
        int c = dfs(0, -1);
        
        if (c % 2 == 1) {
            cout << "-1\n";
        } else {
            cout << ans << "\n";
        }
    }
    
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1086 ms 3012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3284 KB Output is correct
2 Correct 14 ms 3264 KB Output is correct
3 Correct 55 ms 14496 KB Output is correct
4 Correct 44 ms 12584 KB Output is correct
5 Correct 61 ms 16776 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4052 KB Output is correct
2 Correct 12 ms 4116 KB Output is correct
3 Correct 43 ms 20492 KB Output is correct
4 Correct 61 ms 21336 KB Output is correct
5 Correct 47 ms 18584 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 3868 KB Output is correct
2 Correct 408 ms 3400 KB Output is correct
3 Correct 535 ms 3028 KB Output is correct
4 Correct 561 ms 3620 KB Output is correct
5 Correct 557 ms 3876 KB Output is correct
6 Correct 613 ms 3672 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 13808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1086 ms 3012 KB Time limit exceeded
3 Halted 0 ms 0 KB -