oj.uz

Submission #808783

# Submission time Handle Problem Language Result Execution time Memory
808783 2023-08-05T10:58:47 Z DJeniUp Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 277 ms 24360 KB 
#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;
}

Compilation message

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 67 ms 10044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 8560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9160 KB Output is correct
2 Correct 51 ms 9168 KB Output is correct
3 Correct 87 ms 24360 KB Output is correct
4 Correct 133 ms 23908 KB Output is correct
5 Correct 71 ms 22832 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10540 KB Output is correct
2 Incorrect 29 ms 9752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 14312 KB Output is correct
2 Incorrect 98 ms 14164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 19736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 67 ms 10044 KB Output isn't correct
3 Halted 0 ms 0 KB -