제출 #808783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
808783		DJeniUp	Spring cleaning (CEOI20_cleaning)	C++17	9 / 100	277 ms	24360 KiB

cleaning

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")

using namespace std;

typedef int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ld>pairld;

typedef pair<string,ll>pairsl;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 100000000000007
#define eps 0.00000000001
//#define A 30011
#define PI 3.14159265359

ll n,q,sz[N],pard,h,par[N],num[N],nh[N],res,u[N],o;

struct HLD{
    ll sz,p;
}hld[N];

vector<ll>v[N],t[N],push[N];

void dfs1(ll x,ll y){
    //cout<<x<<" "<<y<<endl;
    sz[x]=1;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y){
            dfs1(v[x][i],x);
            sz[x]+=sz[v[x][i]];
            u[x]=(u[x]+u[v[x][i]])%2;
        }
    }
    par[x]=y;
    if(v[x].size()==1){
        u[x]=1;
        o++;
    }
    res+=u[x];
    return ;
}

void S(ll x,ll y,ll z){
    hld[z].sz++;
    nh[x]=z;
    if(nh[x]!=nh[y]){
        num[x]=1;
    }else num[x]=num[y]+1;
    ll mx=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y){
            mx=max(mx,sz[v[x][i]]);
        }
    }
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y){
            if(mx==sz[v[x][i]]){
                S(v[x][i],x,z);
            }else{
                h++;
                hld[h].p=v[x][i];
                S(v[x][i],x,h);
            }
        }
    }
    return ;
}
void Push(ll x,ll y,ll l,ll r){
    if(l==r){
        t[y][x]^=1;
    }else{
        push[y][x]^=1;
        t[y][x]=(r-l+1)-t[y][x];
    }
    return ;
}

void Add(ll x,ll y,ll l,ll r,ll tl,ll tr){
    if(r<tl || tr<l)return ;
    if(tl<=l && r<=tr){
        if(l==r){
            t[y][x]^=1;
        }else{
            push[y][x]^=1;
            t[y][x]=(r-l+1)-t[y][x];
        }
        return ;
    }
    ll m1=(l+r)/2;
    if(push[y][x]!=0){
        push[y][x]=0;
        Push(x*2+1,y,l,m1);
        Push(x*2+2,y,m1+1,r);
    }
    Add(x*2+1,y,l,m1,tl,tr);
    Add(x*2+2,y,m1+1,r,tl,tr);
    t[y][x]=t[y][x*2+1]+t[y][x*2+2];
    return ;
}

void A(ll x){
    if(x==0)return ;
    //cout<<x<<" "<<hld[nh[x]].p<<endl;
    res-=t[nh[x]][0];
    Add(0,nh[x],1,hld[nh[x]].sz,1,num[x]);
    res+=t[nh[x]][0];
    A(par[hld[nh[x]].p]);
    return ;
}

int main(){

    cin>>n>>q;
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        if(v[i].size()>1)pard=i;
    }
   // cout<<pard<<endl;
    dfs1(pard,0);
    //cout<<1<<endl;
    h++;
    hld[h].p=pard;
    S(pard,0,h);
    for(int i=1;i<=h;i++){
        t[i].resize(4*hld[i].sz);
        push[i].resize(4*hld[i].sz);
    }
    for(int i=1;i<=n;i++){
        if(u[i]==1)Add(0,nh[i],1,hld[nh[i]].sz,num[i],num[i]);
        //cout<<i<<" "<<u[i]<<" "<<nh[i]<<" "<<num[i]<<endl;
    }
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        vector<ll>y;
        y.clear();
        for(int j=1;j<=x;j++){
            ll z;
            cin>>z;
            y.pb(z);
        }
        for(int j=0;j<x;j++){
            if(sz[y[j]]==1){
                o--;
            }else A(y[j]);
            sz[y[j]]++;
        }
        //cout<<res<<endl;
        if((o+x)%2==0)cout<<n*2-2-res+x<<endl;
        else cout<<-1<<endl;

        for(int j=0;j<x;j++){
            sz[y[j]]--;
            if(sz[y[j]]==1){
                    o++;
            }else A(y[j]);
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cleaning.cpp: In function 'void dfs1(ll, ll)':
cleaning.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
cleaning.cpp: In function 'void S(ll, ll, ll)':
cleaning.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
cleaning.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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