oj.uz

Submission #468446

# Submission time Handle Problem Language Result Execution time Memory
468446 2021-08-28T10:34:48 Z blue Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 22372 KB 
#include <iostream>
#include <vector>
using namespace std;

int N;
int Q;

vector< vector<int> > E;
vector< vector<int> > edge;

vector<int> leafcount;
vector<int> visit;

void dfs(int u)
{
    if(edge[u].size() == 1)
    {
        leafcount[u] = 1;
    }
    else
    {
        leafcount[u] = 0;
        for(int v: edge[u])
        {
            if(visit[v]) continue;
            visit[v] = 1;
            dfs(v);
            leafcount[u] += leafcount[v];
        }
    }
}

int main()
{
    cin >> N >> Q;
    E = vector< vector<int> >(N, vector<int>(0));

    for(int e = 1; e <= N-1; e++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        E[u].push_back(v);
        E[v].push_back(u);
    }

    for(int q = 1; q <= Q; q++)
    {
        edge = E;

        int D;
        cin >> D;

        for(int x = 0; x < D; x++)
        {
            int a;
            cin >> a;
            a--;

            edge[a].push_back(N+x);
            edge.push_back(vector<int>(1, a));
        }

        if(N == 1 && D == 1)
        {
            cout << 1 << '\n';
        }
        else
        {
            N += D;

            leafcount = vector<int>(N, 0);
            visit = vector<int>(N, 0);

            int rt = 0;
            while(edge[rt].size() == 1)
                rt++;

            visit[rt] = 1;
            dfs(rt);

            if(leafcount[rt] % 2 == 1)
            {
                cout << "-1\n";
            }
            else
            {
                int res = 0;
                for(int i = 0; i < N; i++)
                {
                    if(i == rt) continue;
                    if(leafcount[i] % 2 == 0)
                        res += 2;
                    else
                        res += 1;
                }

                cout << res << '\n';
            }

            N -= D;
        }
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 1063 ms 3952 KB Time limit exceeded

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6500 KB Output is correct
2 Correct 38 ms 6460 KB Output is correct
3 Correct 84 ms 15080 KB Output is correct
4 Correct 119 ms 16612 KB Output is correct
5 Correct 145 ms 19736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7684 KB Output is correct
2 Correct 43 ms 7708 KB Output is correct
3 Correct 106 ms 17848 KB Output is correct
4 Correct 162 ms 22372 KB Output is correct
5 Correct 96 ms 16004 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 3872 KB Output is correct
2 Correct 243 ms 3564 KB Output is correct
3 Correct 327 ms 3180 KB Output is correct
4 Correct 369 ms 3316 KB Output is correct
5 Correct 339 ms 3348 KB Output is correct
6 Correct 404 ms 4076 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 9924 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 1098 ms 15008 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 204 KB Output is correct
2 Execution timed out 1063 ms 3952 KB Time limit exceeded