oj.uz

Submission #430153

# Submission time Handle Problem Language Result Execution time Memory
430153 2021-06-16T11:43:33 Z Ozy Spring cleaning (CEOI20_cleaning) C++17
0 / 100
 1000 ms 11864 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (lli i = (a); i <= (b); i++)
#define repa(i,a,b) for (lli i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000

lli n,a,b,q,d,res,total,raiz;
vector<lli> hijos[MAX+2];
lli val[MAX+2],borr[MAX+2],padres[MAX+2];

lli DFS(lli pos) {

    if (hijos[pos].size() == 1) return 1;

    for (auto h : hijos[pos]) {
        if (h == padres[pos]) continue;
        padres[h] = pos;
        val[pos] += DFS(h);
    }

    res = !(val[pos] % 2) ? res + 1 : res;
    return val[pos];

}

void agrega(lli pos) {

    while (pos > 0) {
        borr[pos]++;

        if (borr[pos] == 1) break;

        if (borr[pos]%2) --total;
        else  ++total;

        pos = padres[pos];
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);

        if (raiz != 0) continue;
        if (hijos[a].size() > 1) raiz = a;
        if (hijos[b].size() > 1) raiz = b;
    }

    res = 0;
    a = DFS(raiz);
    res += n - 1;

    if (!(val[raiz] % 2)) --res;

    rep(Q,1,q) {

        rep(i,1,n) borr[i] = val[i];
        total = res;

        cin >> d;
        rep(i,1,d) {
            cin >> a;
            total++;
            agrega(a);
        }

        if (borr[raiz] % 2) cout << -1 << "\n";
        else cout << total << "\n";

    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 62 ms 4548 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 3536 KB Output is correct
2 Correct 369 ms 3632 KB Output is correct
3 Correct 172 ms 11744 KB Output is correct
4 Execution timed out 1082 ms 11864 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 8516 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 10448 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 2636 KB Output is correct
2 Incorrect 62 ms 4548 KB Output isn't correct