oj.uz

Submission #965236

# Submission time Handle Problem Language Result Execution time Memory
965236 2024-04-18T08:46:28 Z RaulAndrei01 Spring cleaning (CEOI20_cleaning) C++17
16 / 100
 1000 ms 30708 KB 
#include<iostream>
#include<vector>
#include<cassert>

using namespace std;
const int NMAX = 1e5;
vector<int> adj[2 * NMAX+1];
int leafes[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 1 ms 5212 KB Output is correct
2 Execution timed out 1037 ms 6608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6748 KB Output is correct
2 Correct 18 ms 6748 KB Output is correct
3 Execution timed out 1042 ms 22292 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7260 KB Output is correct
2 Correct 21 ms 7252 KB Output is correct
3 Runtime error 67 ms 30708 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 7080 KB Output is correct
2 Correct 112 ms 6524 KB Output is correct
3 Correct 161 ms 6076 KB Output is correct
4 Correct 210 ms 6492 KB Output is correct
5 Correct 163 ms 6492 KB Output is correct
6 Correct 216 ms 7040 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 8444 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 1049 ms 9948 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 5212 KB Output is correct
2 Execution timed out 1037 ms 6608 KB Time limit exceeded
3 Halted 0 ms 0 KB -