oj.uz

Submission #987102

# Submission time Handle Problem Language Result Execution time Memory
987102 2024-05-21T21:38:25 Z aykhn Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 22612 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 2e5 + 5;

int n, q, r;
vector<int> adj[MXN];
int cnt[MXN], add[MXN], leaf, res;

void dfs(int a, int p)
{
    cnt[a] = 0;
    int f = 1;
    for (int v : adj[a])
    {
        if (v == p) continue;
        f = 0;
        dfs(v, a);
        cnt[a] += cnt[v];
        if (cnt[v] & 1) res++;
        else res += 2;
    }
    leaf += f;
    cnt[a] += f;
}

signed main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) 
    {
        if (adj[i].size() >= 2) 
        {
            r = i;
            break;
        }
    }
    for (int i = 1; i <= q; i++)
    {
        set<int> s;
        int d;
        cin >> d;
        for (int j = 1; j <= d; j++)
        {
            int x;
            cin >> x;
            add[x]++;
            s.insert(x);
        }
        int m = n;
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= add[j]; k++) 
            {
                adj[j].push_back(++n);
            }
        }
        res = leaf = 0;
        dfs(r, r);
        if (leaf & 1) cout << -1 << '\n';
        else cout << res << '\n';
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= add[j]; k++) 
            {
                adj[j].pop_back(), n--;
            }
            add[j] = 0;
        }
    }
}

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9048 KB Output is correct
2 Correct 13 ms 9052 KB Output is correct
3 Correct 20 ms 12392 KB Output is correct
4 Correct 45 ms 14256 KB Output is correct
5 Correct 53 ms 15816 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9820 KB Output is correct
2 Correct 14 ms 10076 KB Output is correct
3 Correct 32 ms 18780 KB Output is correct
4 Correct 62 ms 22612 KB Output is correct
5 Correct 28 ms 17592 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9804 KB Output is correct
2 Correct 123 ms 9644 KB Output is correct
3 Correct 162 ms 9208 KB Output is correct
4 Correct 195 ms 9648 KB Output is correct
5 Correct 171 ms 9944 KB Output is correct
6 Correct 211 ms 10312 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 9912 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 1039 ms 12116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

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