oj.uz

Submission #963990

# Submission time Handle Problem Language Result Execution time Memory
963990 2024-04-16T07:14:24 Z Darren0724 Spring cleaning (CEOI20_cleaning) C++17
28 / 100
 1000 ms 16088 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int leaves=0;
int n,q;
struct segtree{
    struct info{
        int cnt0=0,cnt1=0,lz=0;
        int rcnt0(){return (lz?cnt1:cnt0);}
        int rcnt1(){return (lz?cnt0:cnt1);}
    }v[N<<2];
    info pull(info a,info b){
        return {a.rcnt0()+b.rcnt0(),a.rcnt1()+b.rcnt1(),0};
    }
    void push(int id){
        v[id<<1].lz^=v[id].lz;
        v[id<<1|1].lz^=v[id].lz;
        v[id].lz=0;
    }
    void build(int id,int l,int r){
        if(r-l==1){
            v[id].cnt0=1;
            return;
        }
        int m=(l+r)>>1;
        build(id<<1,l,m);
        build(id<<1|1,m,r);
        v[id]=pull(v[id<<1],v[id<<1|1]);
    }
    void add(int id,int a,int b,int l,int r){
        //cout<<id<<' '<<a<<' '<<b<<' '<<l<<' '<<r<<endl;
        if(a<=l&&b>=r){
            v[id].lz^=1;
            return;
        }
        int m=(l+r)>>1;
        push(id);
        if(a<m)add(id<<1,a,b,l,m);
        if(b>m)add(id<<1|1,a,b,m,r);
        v[id]=pull(v[id<<1],v[id<<1|1]);
    }
    int ask(){
        return v[1].rcnt0();
    }
}tr;
vector<int> adj[N],big(N,-1),sz(N,0),pa(N),deg(N,0),gp(N,0);
vector<int> path,place(N,0);
void dfs(int k){
    if(deg[k]==1)sz[k]=1;
    for(int j:adj[k]){
        if(j==pa[k])continue;
        pa[j]=k;
        dfs(j);
        sz[k]+=sz[j];
        big[k]=(big[k]==-1||sz[big[k]]<sz[j]?j:big[k]);
    }
}   
void dfs2(int k){
    place[k]=path.size();
    path.push_back(k);
    if(big[k]!=-1){
        gp[big[k]]=gp[k];
        dfs2(big[k]);
    }
    for(int j:adj[k]){
        if(j!=big[k]&&j!=pa[k]){
            gp[j]=j;
            dfs2(j);
        }
    }
}

void add1(int p,int x){
    //cout<<p<<' '<<x<<endl;
    /*for(int i=p;i>0;i=pa[gp[i]]){
        tr.add(1,place[gp[i]],place[i]+1,0,N);
    }*/
    for(int i=p;i>0;i=pa[i]){
        //cout<<place[i]<<endl;
        tr.add(1,place[i],place[i]+1,0,n);
    }
}
void add(int p,int x){
    if(x==1&&deg[p]==1){
        leaves--;
        return;
    }
    if(x==-1&&deg[p]==1){
        leaves++;
        return;
    }
    add1(p,x);
}
int32_t main(){
    cin>>n>>q;
    tr.build(1,0,n);
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int rt=1;
    for(int i=1;i<=n;i++){
        deg[i]=adj[i].size();
        if(deg[i]>=2){
            rt=i;
        }
        else{
            leaves++;
        }
    }
    gp[rt]=rt;
    dfs(rt);
    dfs2(rt);
    
    for(int i=1;i<=n;i++){
        if(deg[i]==1)add1(i,1);
    }
    /*for(auto [a,b,c]:tr.v){
        cout<<a<<' '<<b<<' '<<c<<endl;
    }*/
    for(int i=0;i<q;i++){
        int t;cin>>t;
        vector<int> a(t);
        for(int j=0;j<t;j++){
            cin>>a[j];
            add(a[j],1);
            deg[a[j]]++;
        }
        int ans=n-2+t+tr.ask();
        int leaf=leaves+t;
        for(int j=0;j<t;j++){
            deg[a[j]]--;
            add(a[j],-1);
        }
        if(leaf&1){
            cout<<-1<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 236 ms 7520 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6084 KB Output is correct
2 Correct 45 ms 5980 KB Output is correct
3 Correct 78 ms 13256 KB Output is correct
4 Correct 98 ms 12364 KB Output is correct
5 Correct 112 ms 13780 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1024 ms 6352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 7512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 10596 KB Output is correct
2 Correct 430 ms 10404 KB Output is correct
3 Correct 307 ms 8344 KB Output is correct
4 Correct 428 ms 10256 KB Output is correct
5 Correct 471 ms 10524 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 14524 KB Output is correct
2 Execution timed out 1068 ms 16088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 236 ms 7520 KB Output is correct
3 Correct 46 ms 6084 KB Output is correct
4 Correct 45 ms 5980 KB Output is correct
5 Correct 78 ms 13256 KB Output is correct
6 Correct 98 ms 12364 KB Output is correct
7 Correct 112 ms 13780 KB Output is correct
8 Execution timed out 1024 ms 6352 KB Time limit exceeded
9 Halted 0 ms 0 KB -