제출 #1160617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160617		arkanefury	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	169 ms	46664 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define lb lower_bound
#define F first
#define S second
#define sz size()
#define int long long
#define all(v) v.begin(),v.end()
#define FOR1(x, n) for(int j = x; j <= n; j ++)
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N =  1e6+5;
int a[N], b[N], siz[N], par[N], d[N], t[N*4], tin[N], path[N];
int n,m,sum=0,x,y, ans, r, cnt[N], l, mod = 1e9+7, inf = -1e18, k, root, timer = 1, heavy[N];
string s, str;
vector<int>g[N];
void push(int v, int l, int r){
    if(!d[v])return;
    if(l != r)d[v*2] ^= 1, d[v*2+1] ^= 1;
    t[v] = r-l+1-t[v];
    d[v] = 0;
}
void UPD(int l, int r, int v = 1, int tl = 1, int tr = n){
    push(v, tl, tr);
    if(l <= tl && tr <= r){
        t[v] =  tr-tl+1-t[v];
        d[v*2] ^= 1, d[v*2+1] ^= 1;
        return;
    }
    if(l > tr || tl > r)return;
    int tm =  (tl + tr) >> 1;
    UPD(l, r, v*2, tl, tm), UPD(l, r, v*2+1, tm+1, tr);
    t[v] = t[v*2+1] + t[v*2];
}
void update(int pos){
    while(1){
        if(pos == root || pos == 0)return;
        UPD(tin[path[pos]], tin[pos]);
        pos = path[pos];
        pos = par[pos];
    }
}
void upd(int v, int tl, int tr, int pos){
    if(tl == tr){
        t[v] ++;
        return;
    }
    int tm = (tl + tr) >> 1;
    if( pos <= tm )upd(v*2, tl, tm, pos);
    else upd(v*2+1, tm+1, tr, pos);
    t[v] = t[v*2] + t[v*2+1];
}
void dfs(int v, int p = 0){
    par[v] = p;
    int H = 0;
    for(auto i : g[v]){
        if(i != p){
            dfs(i, v);
            siz[v] += siz[i];
        if(siz[i] > H)heavy[v] = i, H = siz[i];
        }
    }
    if(g[v].sz==1)siz[v] = 1;
}
void HLD(int v, int h){
    path[v] = h;
    tin[v] = timer++;
    if(siz[v] % 2 == 0 && v != root)upd(1, 1, n, tin[v]);
    if( heavy[v] )HLD(heavy[v], h);
    for(auto i : g[v]){
        if(i != par[v] && i != heavy[v])HLD(i, i);
    }
}
void solve(){
    cin >> n >> m;
    FOR(i, 2, n, 1){
        cin >> x >> y;
        g[x].pb(y), g[y].pb(x);
    }
    FOR(i, 1, n, 1){
        if(g[i].sz!=1){
            root = i;
            break;
        }
    }
    int list = 0;
    FOR(i, 1, n, 1)list += (g[i].sz == 1);
    dfs(root);
    tin[root] = timer++;
    for(auto i : g[root])HLD(i, i);
    FOR(i, 1, m, 1){
        cin >> k;
        set<int>st;
        FOR(j, 1, k, 1){
            cin >> x;
            cnt[x]++;
            st.in(x);
        }
        for(auto j : st){
            list += cnt[j] - (g[j].sz == 1);
            if((cnt[j]-(g[j].sz==1))%2)update(j);
        }
        if(list%2){
            cout << "-1\n";
        }
        else cout << t[1] + n + k - 1 << '\n';
        for(auto j : st){
            list -= cnt[j] - (g[j].sz == 1);
            if((cnt[j]-(g[j].sz==1))%2)update(j);
            cnt[j] = 0;
        }
    }
}
signed main(){
    nikita
    int tt = 1;
    if(!tt)cin >> tt;
    FOR(i, 1, tt, 1){
        solve();
    }
}

• 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