Submission #1110749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110749		koukirocks	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	259 ms	35328 KiB

cleaning

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

struct SEG {
    int n;
    vector<int> a;
    vector<int> lz;
    SEG(int _n):n(_n) {
        a.resize(4*n+10);
        lz.resize(4*n+10);
    }
    void init(int l,int r,int id,vector<int> &ans) {
        if (l==r) {
            a[id]=ans[l];
            return;
        }
        int mid=l+r>>1;
        init(l,mid,id<<1,ans);
        init(mid+1,r,id<<1|1,ans);
        a[id]=a[id<<1]+a[id<<1|1];
    }
    void pd(int l,int r,int id) {
        if (l==r) return;
        if (lz[id]) {
            int mid=l+r>>1;
            a[id<<1]=3*(mid-l+1)-a[id<<1];
            a[id<<1|1]=3*(r-mid)-a[id<<1|1];
            lz[id<<1]^=1;
            lz[id<<1|1]^=1;
            lz[id]=0;
        }
    }
    void update(int L,int R,int l,int r,int id) {
        // cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<id<<" u L R l r id\n"<<flush;
        if (L<=l and r<=R) {
            a[id]=3*(r-l+1)-a[id];
            lz[id]^=1;
            return;
        }
        int mid=l+r>>1;
        pd(l,r,id);
        if (L<=mid) update(L,R,l,mid,id<<1);
        if (mid<R) update(L,R,mid+1,r,id<<1|1);
        a[id]=a[id<<1]+a[id<<1|1];
    }
    int query(int L,int R,int l,int r,int id) {
        // cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<id<<" q L R l r id\n"<<flush;
        if (L<=l and r<=R) return a[id];
        int mid=l+r>>1;
        pd(l,r,id);
        int ans=0;
        if (L<=mid) ans+=query(L,R,l,mid,id<<1);
        if (mid<R) ans+=query(L,R,mid+1,r,id<<1|1);
        return ans;
    }
};

void dfs1(int v,int p,vvector<int> &G,vector<int> &hc,vector<int> &sz,vvector<int> &fa,vector<int> &dep) {
    sz[v]=1;
    hc[v]=-1;
    dep[v]=dep[p]+1;
    fa[v][0]=p;
    for (int i=1;i<20;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
    for (int i:G[v]) {
        if (i==p) continue;
        dfs1(i,v,G,hc,sz,fa,dep);
        sz[v]+=sz[i];
        if (hc[v]==-1 or sz[i]>sz[hc[v]]) hc[v]=i;
    }
}

void dfs2(int v,int p,vvector<int> &G,vector<int> &head,int hd,vector<int> &hc,vector<int> &dfn,int &tm) {
    head[v]=hd;
    dfn[v]=tm++;
    if (hc[v]!=-1) dfs2(hc[v],v,G,head,hd,hc,dfn,tm);
    for (int i:G[v]) {
        if (i==p or i==hc[v]) continue;
        dfs2(i,v,G,head,i,hc,dfn,tm);
    }
}

void dfs3(int v,int p,vvector<int> &G,vector<int> &lvc,vector<int> &dfn) {
    lvc[dfn[v]]=(G[v].size()==1);
    for (int i:G[v]) {
        if (i==p) continue;
        dfs3(i,v,G,lvc,dfn);
        lvc[dfn[v]]+=lvc[dfn[i]];
    }
    if (lvc[dfn[v]]&1) lvc[dfn[v]]=1;
    else lvc[dfn[v]]=2;
}

int get(int v,vector<int> &head,vector<int> &dfn,SEG &seg,vvector<int> &fa,int n) {
    int ans=0;
    while (v) {
        ans+=seg.query(dfn[head[v]],dfn[v],1,n,1);
        v=fa[head[v]][0];
    }
    return ans;
}

void rev(int v,vector<int> &head,vector<int> &dfn,SEG &seg,vvector<int> &fa,int n) {
    while (v) {
        seg.update(dfn[head[v]],dfn[v],1,n,1);
        v=fa[head[v]][0];
    }
}

int main() {
    speed;
    int n,q;
    cin>>n>>q;
    vvector<int> G(n+1);
    int rt=0;
    for (int i=0;i<n-1;i++) {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ttlv=0;
    for (int i=1;i<=n;i++) {
        if (G[i].size()>1) rt=i;
        else ttlv++;
    }
    vector<int> head(n+1),hc(n+1),dfn(n+1),sz(n+1),dep(n+1);
    vvector<int> fa(n+1,vector<int>(20));
    int tm=1;
    dfs1(rt,0,G,hc,sz,fa,dep);
    // cout<<"D1\n"<<flush;
    dfs2(rt,0,G,head,rt,hc,dfn,tm);
    // cout<<"D2\n"<<flush;
    SEG seg(n);
    vector<int> lvc(n+1);
    dfs3(rt,0,G,lvc,dfn);
    // cout<<"D3\n"<<flush;
    seg.init(1,n,1,lvc);
    // cout<<"segD\n"<<flush;
    ll ans=seg.query(1,n,1,n,1);
    // cout<<"segQ\n"<<flush;
    while (q--) {
        int d;
        cin>>d;
        vector<int> nds(d);
        map<int,int> exd;
        for (int &i:nds) cin>>i;
        int dta=0;
        int dtl=0;
        for (int i:nds) {
            if (G[i].size()+exd[i]!=1) {
                dta+=3*dep[i]-2*get(i,head,dfn,seg,fa,n);
                rev(i,head,dfn,seg,fa,n);
            }
            exd[i]++;
        }
        for (auto [i,x]:exd) {
            dtl+=x;
            dtl-=(G[i].size()==1);
        }
        if ((ttlv+dtl)&1) cout<<"-1\n";
        else cout<<ans+dta-seg.query(dfn[rt],dfn[rt],1,n,1)+d<<"\n";
        for (int i:nds) {
            exd[i]--;
            if (G[i].size()+exd[i]!=1) {
                rev(i,head,dfn,seg,fa,n);
            }
        }
    }
    return 0;
}

/*
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
*/

Compilation message (stderr)

cleaning.cpp: In member function 'void SEG::init(int, int, int, std::vector<int>&)':
cleaning.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid=l+r>>1;
      |                 ~^~
cleaning.cpp: In member function 'void SEG::pd(int, int, int)':
cleaning.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid=l+r>>1;
      |                     ~^~
cleaning.cpp: In member function 'void SEG::update(int, int, int, int, int)':
cleaning.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid=l+r>>1;
      |                 ~^~
cleaning.cpp: In member function 'int SEG::query(int, int, int, int, int)':
cleaning.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid=l+r>>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