Submission #1234958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234958		t_holl	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1095 ms	22724 KiB

cleaning

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 1e18;

vector<int> vp;
vector<vector<int>> roads;

pair<int, int> compute (int node, int parent) {
    vector<int> dp1, dp2;

    int oblig = 0;
    int oblig_cnt = 0;

    for (int next : roads[node]) if (next != parent) {
        pair<int, int> sub = compute(next, node);

        if (sub.first == INF) {
            oblig += sub.second;
            oblig_cnt += 2;
        } else if (sub.second == INF) {
            oblig += sub.first;
            oblig_cnt ++;
        } else {
            dp1.push_back(sub.first);
            dp2.push_back(sub.second);
        }
    }

    for (int i = 0; i < vp[node]; i ++) {
        oblig ++;
        oblig_cnt ++;
    }

    if (dp1.size() + oblig_cnt == 0) {
        return { 1, INF };
    }

    vp[node] = 0;

    int mvr = 0;
    for (int u : dp1) mvr = u;
    int mpr = INF;
    for (int i = 0; i < dp1.size(); i ++)
        mpr = min(mpr, dp2[i] - dp1[i]);
    
    int np1 = mvr + oblig;
    int np2 = mvr + mpr + oblig;
    if (((dp1.size() + oblig_cnt) & 1) == 0) swap(np1, np2);

    np1 ++;
    np2 += 2;

    if (np1 >= INF) np1 = INF;
    if (np2 >= INF) np2 = INF;

    assert(np1 == INF || np2 == INF);

    return { np1, np2 };
}

void solve () {
    int N, Q; cin >> N >> Q;

    vp.resize(N);
    roads.resize(N);

    vector<int> deg(N);

    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        roads[a].push_back(b);
        roads[b].push_back(a);
        deg[a] ++; deg[b] ++;
    }

    int root = 0;
    for (; root < N; root ++)
        if (deg[root] != 1)
            break ;
    
    for (int i = 0; i < Q; i ++) {
        int d;
        cin >> d;

        for (int j = 0; j < d; j ++) {
            int x;
            cin >> x;
            x --;

            vp[x] ++;
        }

        pair<int, int> U = compute(root, -1);

        int res = U.second;

        if (res >= INF) cout << -1 << "\n";
        else cout << (res - 2) << "\n";
    }
}

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

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

• 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