oj.uz

Submission #963517

# Submission time Handle Problem Language Result Execution time Memory
963517 2024-04-15T08:37:40 Z Ghetto Spring cleaning (CEOI20_cleaning) C++17
34 / 100
 1000 ms 21048 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
 
int old_n, q;
int n;
vector<int> adj[MAX_N];
int n_added[MAX_N];
int n_ls[MAX_N];
int ans;
void dfs(int u, int par) {
    n_ls[u] = (adj[u].size() == 1) ? 1 : 0;
 
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        n_ls[u] += n_ls[v];        
    }
 
    n_ls[u] %= 2;
    if (par != -1 && n_ls[u] == 0) n_ls[u] = 2; 
    ans += n_ls[u];
}
 
void init() {
    ans = 0;
}
void do_query(int query) {
    int d_n; cin >> d_n;
    n = old_n + d_n;
    init();
    for (int u = old_n + 1; u <= n; u++) {
        int v; cin >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        n_added[u]++;
        n_added[v]++;
    }
 
    for (int u = 1; u <= n; u++) {
        if (adj[u].size() == 1) continue;
        
        dfs(u, -1);
        if (n_ls[u]) cout << "-1" << '\n';
        else cout << ans << '\n';
 
        for (int v = 1; v <= n; v++) {
            while (n_added[v]) {
                adj[v].pop_back();
                n_added[v]--;
            }
        }
        return;    
    }
}
 
int main() {
    // freopen("spring.in", "r", stdin);
 
    cin.sync_with_stdio(false);
    cin.tie(0);
 
    cin >> old_n >> q;
    for (int i = 1; i < old_n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    for (int i = 1; i <= q; i++) do_query(i);
}

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9560 KB Output is correct
2 Correct 17 ms 9564 KB Output is correct
3 Correct 23 ms 10196 KB Output is correct
4 Correct 31 ms 11976 KB Output is correct
5 Correct 42 ms 13012 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10076 KB Output is correct
2 Correct 16 ms 10648 KB Output is correct
3 Correct 29 ms 18776 KB Output is correct
4 Correct 48 ms 21048 KB Output is correct
5 Correct 27 ms 17492 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 8100 KB Output is correct
2 Correct 117 ms 7804 KB Output is correct
3 Correct 157 ms 7260 KB Output is correct
4 Correct 222 ms 8056 KB Output is correct
5 Correct 179 ms 8024 KB Output is correct
6 Correct 237 ms 8368 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1024 ms 8536 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 1053 ms 9820 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 6488 KB Output is correct
2 Execution timed out 1069 ms 7260 KB Time limit exceeded
3 Halted 0 ms 0 KB -