제출 #1039089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039089		Tonyl	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1076 ms	13400 KiB

cleaning

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