oj.uz

Submission #965241

# Submission time Handle Problem Language Result Execution time Memory
965241 2024-04-18T08:47:34 Z RaulAndrei01 Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 ms 16372 KB 
#include<iostream>
#include<vector>
#include<cassert>

using namespace std;
const int NMAX = 1e5;
vector<int> adj[2 * NMAX+1];
int leafes[2 * NMAX+1];
int root = -1;
int ans;

void dfs (int nod , int par)
{
    if (adj[nod].size() <= 1) leafes[nod] = 1;
    else leafes[nod] = 0;
    for (auto &to : adj[nod])
    {
        if (to != par) {
            dfs(to , nod);
            leafes[nod] += leafes[to];
        }
    }
    if (leafes[nod] % 2 == 0 && nod != root) ans++;
}

int main ()
{
    int n , q; cin >> n >> q;
    for (int i = 2; i <= n; i++)
    {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (adj[i].size() > 1) root = i;
    }
    assert(root != -1);
    while (q--)
    {
        int d; cin >> d;
        vector<int> a(d);
        for (int i = 0; i < d; i++)
        {
            cin >> a[i];
            adj[a[i]].push_back(n+i+1);
        }

        ans = 0;
        dfs(root , 0);
        cout << ((leafes[root] % 2 == 0) ? n + d - 1 + ans : -1) << '\n';

        for (int i = 0; i < d; i++)
        {
            adj[a[i]].pop_back();
        }
    }

    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6816 KB Output is correct
2 Correct 18 ms 6748 KB Output is correct
3 Correct 41 ms 9276 KB Output is correct
4 Correct 57 ms 9672 KB Output is correct
5 Correct 70 ms 11076 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7256 KB Output is correct
2 Correct 20 ms 7268 KB Output is correct
3 Correct 55 ms 15188 KB Output is correct
4 Correct 75 ms 16372 KB Output is correct
5 Correct 58 ms 15304 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 6836 KB Output is correct
2 Correct 137 ms 6540 KB Output is correct
3 Correct 164 ms 6232 KB Output is correct
4 Correct 202 ms 6744 KB Output is correct
5 Correct 160 ms 6744 KB Output is correct
6 Correct 218 ms 6920 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 8148 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 1090 ms 8984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

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