Submission #1325750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325750		shirokuma5	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1095 ms	8936 KiB

cleaning

/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)

template<class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b; return 1;
    }
    return 0;
}
template<class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b; return 1;
    }
    return 0;
}
struct edge {
    int to, w;
};
ll inv(ll a) {
    ll b = mod, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= b * t;
        swap(a, b);
        u -= v * t;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
template<class T> void print(vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
    return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
    T x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
    return (bit < (1LL << N));
}
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

vector<vector<int>> G;
vector<int> par;
void dfs(int now, int pre = -1) {
    for (int nex : G[now]) {
        if (nex == pre) continue;
        par[nex] = now; dfs(nex, now);
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q; cin >> n >> q;
    par.assign(n + 1, -1);
    G.resize(n + 1);
    rep(i, n-1) {
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }

    int r = 1;
    vector<int> deg(n + 1), seen(n + 1, 0);
    vector<int> sorted;
    queue<int> todo;
    rep1(i, n) {
        deg[i] = G[i].size();
        if (deg[i] == 1) todo.push(i);
    }
    while (!todo.empty()) {
        r = todo.front(); todo.pop(); seen[r] = 1;
        sorted.push_back(r);
        for (int nex : G[r]) {
            if (seen[nex] == 1) par[nex] = r;
            else if (--deg[nex] == 1) todo.push(nex);
        }
    }

    while (q--) {
        int d; cin >> d;
        vector<int> a(d);
        rep(i, d) cin >> a[i];
        ll res = 0;

        vector<int> chi(n + 1, 0);
        rep(i, d) {
            chi[a[i]]++; res++;
        }
        rep1(i, n) if (chi[i] == 0 && G[i].size() == 1) {
            chi[i] = 1;
        }

        for (int v : sorted) {
            if (par[v] == -1) {
                if (chi[v] % 2 == 1) res = -1;
            }
            else {
                if (chi[v] % 2 == 0) chi[v] = 2;
                else chi[v] = 1;
                res += chi[v]; chi[par[v]] += chi[v];
            }
        }

        cout << res << endl;


    }

}

• 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