Submission #868684

#	Time	Username	Problem	Language	Result	Execution time	Memory
868684		ToighetLPHM	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	725 ms	22032 KiB

cleaning

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 100005
using namespace std;
int n,q,pos[N],numchild[N],head[N],depth[N],dad[N],numleaf[N],leaf=0,Time=0;
char tv;
vector < int > adj[N];
struct seg {
    int cnt0,cnt1,lazy;
} T[4*N];
void dfs (int u,int par) {
    dad[u]=par;
    numchild[u]=1;
    int posmax=0,maxchild=0;
    FOR(i,0,adj[u].size()-1) {
        int v=adj[u][i];
        if (v!=par) {
            dfs(v,u);
            numchild[u]+=numchild[v];
            numleaf[u]+=numleaf[v];
            posmax = (numchild[v]>maxchild) ? i : posmax;
            maxchild = (numchild[v]>maxchild) ? numchild[v] : maxchild;
        }
    }
    swap(adj[u][0],adj[u][posmax]);
    if (numchild[u]==1) {
        ++leaf;
        numleaf[u]=1;
    }
}
int node[N];
void HLD (int u) {
    pos[u]=++Time;
    node[Time]=u;
    for (auto v : adj[u])
    if (dad[v]==u) {
        if (numchild[v]*2>=numchild[u]) {
            head[v]=head[u];
            depth[v]=depth[u];
        }
        else {
            head[v]=v;
            depth[v]=depth[u]+1;
        }
        HLD(v);
    }
}
void Build(int id,int l,int r) {
    if (l==r) {
        T[id].cnt0=(numleaf[node[l]]%2==0);
        T[id].cnt1=(numleaf[node[l]]%2==1);
        T[id].lazy=0;
        return;
    }
    int mid=(l+r)/2;
    Build(id*2,l,mid);
    Build(id*2+1,mid+1,r);
    T[id].cnt0=T[id*2].cnt0+T[id*2+1].cnt0;
    T[id].cnt1=T[id*2].cnt1+T[id*2+1].cnt1;
    T[id].lazy=0;
}
void down (int id) {
    if (T[id].lazy%2==0) return;
    swap(T[id*2].cnt0,T[id*2].cnt1);
    T[id*2].lazy=T[id*2].lazy+T[id].lazy;
    //
    swap(T[id*2+1].cnt0,T[id*2+1].cnt1);
    T[id*2+1].lazy=T[id*2+1].lazy+T[id].lazy;
    //
    T[id].lazy=0;
}
void update (int id,int l,int r,int c,int d,int x) {
    if (r<c || l>d) return;
    if (c<=l && r<=d) {
        swap(T[id].cnt0,T[id].cnt1);
        T[id].lazy=T[id].lazy+x;
        return;
    }
    down(id);
    int mid=(l+r)/2;
    update(id*2,l,mid,c,d,x);
    update(id*2+1,mid+1,r,c,d,x);
    T[id].cnt0=T[id*2].cnt0+T[id*2+1].cnt0;
    T[id].cnt1=T[id*2].cnt1+T[id*2+1].cnt1;
}
void incroad (int u,int v,int x) {
    if (depth[u]>depth[v]) swap(u,v);
    while (depth[v]>depth[u]) {
        update(1,1,n,pos[head[v]],pos[v],x);
        v=head[v];
        v=dad[v];
    }
    while (head[u]!=head[v]) {
        update(1,1,n,pos[head[u]],pos[u],x);
        u=head[u];
        u=dad[u];
        update(1,1,n,pos[head[v]],pos[v],x);
        v=head[v];
        v=dad[v];
    }
    if (pos[u]<pos[v]) update(1,1,n,pos[u],pos[v],x);
    else update(1,1,n,pos[v],pos[u],x);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    FOR(i,1,n-1) {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int root;
    FOR(i,1,n)
    if (adj[i].size()>1) root=i;
    //cout<<root<<'\n';
    dfs(root,root);
    head[root]=root;
    HLD(root);
    Build(1,1,n);
    //cout<<T[1].cnt0<<'\n';
    while (q--) {
        int d;
        cin>>d;
        vector < int > a;
        int e=n-1;
        FOR(i,1,d) {
            int x;
            cin>>x;
            a.pb(x);
            if (numchild[x]==1) {
                --leaf;
                incroad(x,root,1);
            }
            ++numchild[x];
            ++leaf;
            incroad(x,root,1);
            ++e;
        }
        //cout<<e<<" "<<leaf<<'\n';
        if (leaf&1) cout<<-1<<'\n';
        else {
            e+=T[1].cnt0-1;
            cout<<e<<'\n';
        }
        FOR(i,0,d-1) {
            --numchild[a[i]];
            if (numchild[a[i]]==1) {
                ++leaf;
                incroad(a[i],root,-1);
            }
            --leaf;
            incroad(a[i],root,-1);
        }
    }
    return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:2:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define FOR(i,a,b) for (int i=(a);i<=(b);i++)
      |                                    ^
cleaning.cpp:23:5: note: in expansion of macro 'FOR'
   23 |     FOR(i,0,adj[u].size()-1) {
      |     ^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:147:20: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |             incroad(x,root,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