제출 #1167001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167001		windowwife	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	133 ms	20292 KiB

cleaning

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 1;
int n, q, u, v, deg[maxn], r, dp[maxn], D, a[maxn], b[maxn], tot;
int par[maxn], sz[maxn], nxt[maxn], id[maxn], re[maxn], chain[maxn], head[maxn], cc = 1, ct = 0;
vector<int> adj[maxn];
bool ok[maxn];
struct Node
{
    int cnt[2];
    bool lazy;
}st[4*maxn];
void dfs (int u, int p)
{
    par[u] = p;
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[nxt[u]]) nxt[u] = v;
        dp[u] += dp[v];
    }
    if (sz[u] == 1) dp[u] = 1;
}
void hld (int u, int p)
{
    if (head[cc] == 0) head[cc] = u;
    chain[u] = cc;
    id[u] = ++ct;
    re[ct] = u;
    if (nxt[u] != 0) hld(nxt[u], u);
    for (int v : adj[u])
    {
        if (v == p || v == nxt[u]) continue;
        cc++;
        hld(v, u);
    }
}
void build (int node, int l, int r)
{
    if (l == r)
    {
        st[node].cnt[dp[re[l]] & 1] = 1;
        st[node].lazy = false;
        return;
    }
    int m = (l + r)/2;
    build(2*node, l, m);
    build(2*node + 1, m + 1, r);
    st[node].cnt[0] = st[2*node].cnt[0] + st[2*node + 1].cnt[0];
    st[node].cnt[1] = st[2*node].cnt[1] + st[2*node + 1].cnt[1];
}
void down (int node)
{
    if (!st[node].lazy) return;
    swap(st[2*node].cnt[0], st[2*node].cnt[1]);
    swap(st[2*node + 1].cnt[0], st[2*node + 1].cnt[1]);
    st[2*node].lazy ^= 1;
    st[2*node + 1].lazy ^= 1;
    st[node].lazy = false;
}
void upd (int node, int l, int r, int cl, int cr)
{
    if (cr < l || r < cl) return;
    if (cl <= l && r <= cr)
    {
        swap(st[node].cnt[0], st[node].cnt[1]);
        st[node].lazy ^= 1;
        return;
    }
    down(node);
    int m = (l + r)/2;
    upd(2*node, l, m, cl, cr);
    upd(2*node + 1, m + 1, r, cl, cr);
    st[node].cnt[0] = st[2*node].cnt[0] + st[2*node + 1].cnt[0];
    st[node].cnt[1] = st[2*node].cnt[1] + st[2*node + 1].cnt[1];
}
void update (int u)
{
    while (u != 0)
    {
        upd(1, 1, n, id[head[chain[u]]], id[u]);
        u = par[head[chain[u]]];
    }
}
void test (int node, int l, int r)
{
    if (l == r)
    {
        cout << re[l] << ':';
        if (st[node].cnt[0]) cout << 0 << " ";
        else cout << 1 << " ";
        return;
    }
    down(node);
    int m = (l + r)/2;
    test(2*node, l, m);
    test(2*node + 1, m + 1, r);
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v;
        deg[u]++; deg[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 1) r = i;
    dfs(r, 0);
    hld(r, 0);
    /*for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    cout << '\n';
    for (int i = 1; i <= n; i++) cout << id[i] << " ";
    cout << '\n';
    for (int i = 1; i <= n; i++) cout << re[i] << " ";
    cout << '\n';*/
    build(1, 1, n);
    while (q--)
    {
        tot = dp[r];
        cin >> D;
        for (int i = 1; i <= D; i++)
        {
            cin >> a[i];
            b[a[i]]++;
        }
        for (int i = 1; i <= D; i++)
        {
            if (ok[a[i]]) continue;
            ok[a[i]] = true;
            if (deg[a[i]] == 1)
            {
                tot += b[a[i]] - 1;
                if (1 ^ (b[a[i]] & 1)) update(a[i]);
            }
            else
            {
                tot += b[a[i]];
                if (b[a[i]] & 1) update(a[i]);
            }
        }
        //cout << st[1].cnt[0] << " ";
        if (tot & 1) cout << -1 << '\n';
        else cout << n + D + st[1].cnt[0] - 2 << '\n';
        //test(1, 1, n);
        //cout << '\n';
        for (int i = 1; i <= D; i++)
        {
            if (!ok[a[i]]) continue;
            ok[a[i]] = false;
            if (deg[a[i]] == 1)
            {
                if (1 ^ (b[a[i]] & 1)) update(a[i]);
            }
            else
            {
                if (b[a[i]] & 1) update(a[i]);
            }
            b[a[i]] = 0;
        }
        //test(1, 1, n);
        //cout << '\n';
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30