Submission #963517

#	Time	Username	Problem	Language	Result	Execution time	Memory
963517		Ghetto	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1069 ms	21048 KiB

cleaning

#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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30