Submission #1310239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310239		Ludissey	Spring cleaning (CEOI20_cleaning)	C++20	9 / 100	73 ms	22752 KiB

cleaning

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

const int MAX=1e5;
vector<vector<int>> neigh;
vector<int> val;
vector<int> sz;
vector<int> parent;
vector<pair<int,int>> block;
vector<int> indx;
vector<vector<int>> path;
vector<int> seg;
vector<int> lazy;
vector<int> ssz;
int root=0;
int lvs=0;

void dfs(int x, int p){
    val[x]=0;
    sz[x]=0;
    parent[x]=p;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        dfs(u,x);
        sz[x]+=sz[u];
        val[x]+=val[u];
    }
    if(sz(neigh[x])==1) {
        val[x]=1;
        lvs++;
    }
    val[x]=val[x]%2;
}


void hld(int x, int p, int k){
    int mx=-1;
    path[k].push_back(x);
    for (auto u : neigh[x]) {
        if(u==p) continue;
        mx=max(mx, sz[u]);
    }
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        if(sz[u]==mx) hld(u,x,k), mx=-1;
        else path.push_back({}), hld(u,x,sz(path)-1);
    }
    
}

void propagate(int x){
    if(lazy[x]==1){
        lazy[x]=0;
        if(x*2+1<sz(seg)){
            lazy[x*2]=(lazy[x*2]+1)%2;
            seg[x*2]=ssz[x*2]-seg[x*2];
            lazy[x*2+1]=(lazy[x*2+1]+1)%2;
            seg[x*2+1]=ssz[x*2+1]-seg[x*2+1];
        }
    }
}

int query(int x, int l, int r, int ql, int qr){
    if(r<ql||l>qr) return 0;
    if(l>=ql&&r<=qr) return seg[x];
    propagate(x);
    int mid=(l+r)/2;
    return query(x*2, l, mid, ql, qr)+query(x*2+1, mid+1, r, ql, qr);
}

void update(int x, int l, int r, int ql, int qr){
    if(r<ql||l>qr) return;
    if(l>=ql&&r<=qr) {
        lazy[x]=(lazy[x]+1)%2;
        seg[x]=ssz[x]-seg[x];
        return;
    }
    propagate(x);
    int mid=(l+r)/2;
    update(x*2, l, mid, ql, qr);
    update(x*2+1, mid+1, r, ql, qr);
    seg[x]=seg[x*2]+seg[x*2+1];
}

void build(int x, int l, int r){
    lazy[x]=0;
    ssz[x]=r-l+1;
    if(l==r) {
        seg[x]=val[indx[l]];
        return;
    }
    int mid=(l+r)/2;
    build(x*2, l, mid);
    build(x*2+1, mid+1, r);
    seg[x]=seg[x*2]+seg[x*2+1];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,q; cin >> n >> q;
    neigh.resize(n);
    val.resize(n,-1);
    sz.resize(n,-1);
    seg.resize(4*n,-1);
    lazy.resize(4*n,-1);
    ssz.resize(4*n,-1);
    block.resize(n);
    parent.resize(n,-1);
    for (int i = 0; i < n-1; i++)
    {
        int u,v; cin >> u >> v; u--; v--;
        neigh[u].push_back(v);
        neigh[v].push_back(u);
        if(sz(neigh[u])>1) root=u;
        if(sz(neigh[v])>1) root=v;
    }
    dfs(root,-1);
    path.push_back({});
    hld(root,-1,0);
    int s=0;
    for (int k = 0; k < sz(path); k++)
    {
        for (int i = 0; i < sz(path[k]); i++)
        {
            indx.push_back(path[k][i]);
            block[path[k][i]]={s,s+i};
        }
        s+=sz(path[k]);
    }
    int lg=log2(n)+1;
    assert(sz(path)<=lg);
    build(1,0,n-1);
    vector<pair<int,int>> conn(n,{0,0});
    for (int i = 0; i < q; i++)
    {
        int clvs=0;
        int D; cin >> D;
        vector<int> d(D);
        for (int i = 0; i < D; i++) cin >> d[i];
        vector<int> up;
        //cerr << query(1,0,n-1,1,n-1) << " ";
        for (int i = 0; i < D; i++)
        {
            conn[d[i]-1].first++;
            if(conn[d[i]-1].first==1&&sz(neigh[d[i]-1])==1) continue;
            int x=d[i]-1;
            while(x!=-1){
                //cerr << query(1,0,n-1,1,n-1) << " ";
                up.push_back(x);
                conn[x].second++;
                x=parent[indx[block[x].first]];
            }
            clvs++;
        }
        for (auto u : up){
            if(conn[u].second<0||conn[u].second%2==0) continue;
            update(1,0,n-1,block[u].first,block[u].second);
            conn[u].second=-1;
        }
        if((clvs+lvs)%2) cout << -1 << "\n";
        else cout << 2*(n-1)-query(1,0,n-1,1,n-1)+D << "\n";
        for (auto u : up){
            if(conn[u].second==-1) update(1,0,n-1,block[u].first,block[u].second);
            conn[u]={0,0};
        }
        for (int i = 0; i < D; i++) conn[d[i]-1]={0,0};
        cerr << "\n";
    }
    
    return 0;
}   

• 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