oj.uz

Submission #1039089

# Submission time Handle Problem Language Result Execution time Memory
1039089 2024-07-30T12:43:48 Z Tonyl Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 13400 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define submit(a,b) cout << a << " " << b << endl

int n,q;

vector<vi> graph;
vi children;

int total = 0;
int nonleaf = 0;

int calc(int i, int par = -1) {
    if (par == -1) total = 0;

    int fr = 0;
    trav(nei, graph[i]) {
        if (nei == par) continue;
        int o = calc(nei, i);
        total += o; fr += o;
    }
    fr += children[i]; total += children[i];
    if (fr == 0) fr = 1;
    if (fr > 2) fr = 2 - (fr%2);

    return fr;
}

void make_graph() {
    graph.assign(n, vi());
    REP(i,n-1) {
        int u,v; cin >> u >> v; u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    children.assign(n, 0);

    REP(i,n) {
        if (graph[i].size() > 1) nonleaf = i;
    }
}

int query() {
    int d; cin >> d;
    vi added;
    REP(dd, d) {
        int a; cin >> a; a--;
        added.push_back(a);
        children[a]++;
    }
    int fr = calc(nonleaf);
    trav(a, added) children[a] = 0;
    if (fr % 2) return -1;
    else return total;
}

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

    cin >> n >> q;
    make_graph();

    REP(qq, q) {
        cout << query() << "\n";
    }
}

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1496 KB Output is correct
2 Correct 6 ms 1496 KB Output is correct
3 Correct 19 ms 7452 KB Output is correct
4 Correct 22 ms 6612 KB Output is correct
5 Correct 31 ms 8636 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2136 KB Output is correct
2 Correct 5 ms 1932 KB Output is correct
3 Correct 25 ms 13400 KB Output is correct
4 Correct 52 ms 13140 KB Output is correct
5 Correct 26 ms 12380 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 2640 KB Output is correct
2 Correct 95 ms 2064 KB Output is correct
3 Correct 149 ms 1648 KB Output is correct
4 Correct 201 ms 2136 KB Output is correct
5 Correct 148 ms 2136 KB Output is correct
6 Correct 201 ms 2580 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 5052 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 1047 ms 7784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

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