제출 #1247167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247167		mountainsalt	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	150 ms	41028 KiB

cleaning

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

using namespace std;

const int N=2e5+5;

int n,q,id,ans,depth[N],sz[N],leafs[N],hv[N],head[N],par[N],idx[N],idxdeg[N];
int rt=1;
bool leaf[N];
vector<vector<int>> adj(N);

struct {
    struct node{
        int odd,even,lz; // #times that use edge(par[i],i), ans for subtree, lazypropagation
        node():odd(0),even(0),lz(0){}
    };
    node seg[4*N];
    void push(int l,int r,int i){
        if(seg[i].lz){
            seg[i].lz=false;
            swap(seg[i].odd,seg[i].even);
            if(l!=r){
                seg[2*i].lz^=1;
                seg[2*i+1].lz^=1;
            }
        }
    }
    void build(int l,int r,int i){
        if(l==r){
            if(idxdeg[l]) seg[i].odd++;
            else seg[i].even++;
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,2*i),build(mid+1,r,2*i+1);
        seg[i].odd=seg[2*i].odd+seg[2*i+1].odd;
        seg[i].even=seg[2*i].even+seg[2*i+1].even;
    }
    void update(int l,int r,int i,int ll,int rr){
        push(l,r,i);
        if(r<ll||l>rr) return;
        if(l>=ll&&r<=rr) return seg[i].lz=1,push(l,r,i),void();
        int mid=(l+r)/2;
        update(l,mid,2*i,ll,rr),update(mid+1,r,2*i+1,ll,rr);
        seg[i].odd=seg[2*i].odd+seg[2*i+1].odd;
        seg[i].even=seg[2*i].even+seg[2*i+1].even;
    }
    void add(int x){
        while(1){
            update(1, n, 1, idx[head[x]], idx[x]);
            if(head[x]==rt) break;
            x=par[head[x]];
        }
    }
    int query(){ 
        push(1,n,1);
        return seg[1].odd+2*seg[1].even; 
    }
} lazyseg;

int dfs1(int u,int p){
    par[u]=p;
    depth[u]=depth[p]+1;
    sz[u]++;
    leafs[u]=leaf[u];
    int mx=0;
    for(auto v:adj[u]){
        if(v==p) continue;
        sz[u]+=dfs1(v,u);
        leafs[u]+=leafs[v];
        if(sz[v]>mx){
            mx=sz[v];
            hv[u]=v;
        }
    }
    return sz[u];
}

void hld(int u,int p,int h){
    idx[u]=++id;
    head[u]=h;
    if(hv[u]) hld(hv[u],u,h);
    for(auto v:adj[u]){
        if(v==p||v==hv[u]) continue;
        hld(v,u,v);
    }
}

void calculatedfs(int u,int p){
    for(int i=1; i<=n; i++){
        idxdeg[idx[i]]=leafs[i]%2;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    for(int i=n; i>=1; i--){
        if(adj[i].size()==1) leaf[i]=true;
        else rt=i,leaf[i]=false;
    }
    dfs1(rt,rt);
    hld(rt,rt,rt);
    calculatedfs(rt,rt);
    lazyseg.build(1,n,1);
    int __=1;
    bool visited[n+1]; memset(visited, 0, sizeof visited);
    while(__++<=q){
        int d;
        cin >> d;
        int que[d];
        for(auto &e:que) cin >> e;
        int cnt=0;
        for(int i=0; i<d; i++){
            if(leaf[que[i]]&&!visited[que[i]]) visited[que[i]]=true,cnt++;
            else lazyseg.add(que[i]);
        }
        int le=leafs[rt]+d-cnt;
        if(le%2) cout << -1 << "\n";
        else cout << lazyseg.query()+d-2 << "\n";
        for(auto e:que){
            if(leaf[e] && visited[e]) visited[e] = false;
            else lazyseg.add(e);
        }
    }
}

• 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