제출 #545525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545525		leaked	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	572 ms	21624 KiB

cleaning

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const ll inf=1e18;
const int N=1e5+1;
vec<int> g[N];

int dp[N];
int t[4*N][2];
int p[4*N];
int par[N],in[N],out[N],tt=0,ht[N];
int up[N];

int have=0;
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v][0]=1;
    }
    else{
        int tm=(tl+tr)>>1;
        build(2*v,tl,tm);build(2*v+1,tm+1,tr);
        t[v][0]=tr-tl+1;
    }
}
void push(int v,int tl,int tr){
    if(!p[v])
        return;
    for(auto &u : {v<<1,v<<1|1})
        swap(t[u][0],t[u][1]),p[u]^=1;
    p[v]=0;
}
void _xor(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        swap(t[v][0],t[v][1]);
        p[v]^=1;
        return;
    }
    if(tl>r||tr<l)
        return;
    int tm=(tl+tr)>>1;push(v,tl,tr);
    _xor(l,r,2*v,tl,tm);_xor(l,r,2*v+1,tm+1,tr);
    t[v][0]=t[v<<1][0]+t[v<<1|1][0];
    t[v][1]=t[v<<1][1]+t[v<<1|1][1];
}
void dfs1(int v,int p){
    dp[v]=1;
    for(auto &z : g[v]){
        auto it=find(all(g[z]),v);
        g[z].erase(it,it+1);
        par[z]=v;
        dfs1(z,v);
        dp[v]+=dp[z];
        if(dp[z]>dp[g[v][0]])
            swap(z,g[v][0]);
    }
}
void dfs(int v,int who){
    if(who==-1) who=v;
    up[v]=who;
    in[v]=tt++;
    if(!sz(g[v])) ++have;
    for(auto &z : g[v]){
        ht[z]=ht[v]+1;
        dfs(z,who);
        who=-1;
    }
//    cout<<"V "<<v<<' '<<in[v]<<' '<<up[v]<<endl;
    out[v]=tt-1;
}
void addway(int v){
    while(v!=-1){
        assert((ht[v]-ht[up[v]])==(in[v]-in[up[v]]));
//        cout<<"ADD "<<in[up[v]]<<' '<<in[v]<<endl;
        _xor(in[up[v]],in[v],1,0,tt-1);
        v=par[up[v]];
    }
}
signed main(){
    fast_resp;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }

    int root=-1;
    for(int i=0;i<n;i++) root=(sz(g[i])>1?i:root);
    par[root]=-1;

    dfs1(root,root);
    dfs(root,-1);

    build(1,0,tt-1);
    for(int i=0;i<n;i++){
        if(sz(g[i])==0)
            addway(i);
    }
    while(m--){
        int d;
        cin>>d;
        int ans=0;
        vec<int> e;
        int nh=have;
        for(int i=0;i<d;i++){
            int x;
            cin>>x;--x;
            e.pb(x);
            addway(x);
            if(!sz(g[x])) addway(x),--nh;
            g[x].pb(i);
            ++nh;
        }
        ans=n+d-1;ans+=t[1][0];
        cout<<(nh%2?-1:ans-1)<<'\n';
        for(auto &x : e){
            addway(x);
            g[x].pop_back();
            if(!sz(g[x])) addway(x);
        }
    }
    return 0;
}
/*
7 1
1 2
2 4
4 5
5 6
5 7
3 4
2 2 4
1 1

*/

• 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