Submission #927686

#	Time	Username	Problem	Language	Result	Execution time	Memory
927686		12345678	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	166 ms	21116 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, q, dp[nx], sz[nx], id[nx], pa[nx], hd[nx], t, u, v, rt, vs[nx], k[nx];
vector<int> d[nx];

struct segtree
{
    int a[4*nx], b[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        if (!lz[i]) return;
        lz[i]=0;
        swap(a[i], b[i]);
        if (l!=r) lz[2*i]=!lz[2*i], lz[2*i+1]=!lz[2*i+1];        
    }
    void build(int l, int r, int i)
    {
        if (l==r)
        {
            if (k[l]==1) a[i]++;
            else b[i]++;
            return;
        }
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        a[i]=a[2*i]+a[2*i+1];
        b[i]=b[2*i]+b[2*i+1];
    }
    void update(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return;
        if (ql<=l&&r<=qr) return lz[i]=1, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr);
        update(md+1, r, 2*i+1, ql, qr);
        a[i]=a[2*i]+a[2*i+1];
        b[i]=b[2*i]+b[2*i+1];
    }
    bool query(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (r!=1) return query(l, (l+r)/2, 2*i);
        return a[i]==1; 
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) return void(cout<<"show "<<l<<' '<<a[i]<<' '<<b[i]<<'\n');
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
} s;

void dfs(int u, int p)
{
    sz[u]=1;
    pa[u]=p;
    if (d[u].size()==1) dp[u]++;
    for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v], dp[u]+=dp[v];
    dp[u]%=2;
}

void dfshld(int u, int p, int h)
{
    id[u]=++t;
    hd[u]=h;
    pair<int, int> hv={-1, -1};
    for (auto v:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    if (hv.second!=-1) dfshld(hv.second, u, h);
    for (auto v:d[u]) if (v!=p&&v!=hv.second) dfshld(v, u, v);
}

void flip(int u)
{
    //cout<<"update "<<u<<' '<<hd[u]<<' '<<id[u]<<' '<<id[hd[u]]<<'\n';
    s.update(1, n, 1, id[hd[u]], id[u]);
    if (hd[u]==rt) return;
    flip(pa[hd[u]]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) if (d[i].size()>1) rt=i;
    dfs(rt, rt);
    dfshld(rt, rt, rt);
    for (int i=1; i<=n; i++) k[id[i]]=dp[i];
    s.build(1, n, 1);
    //s.show(1, n, 1);
    //for (int i=1; i<=n; i++) cout<<"id "<<i<<' '<<id[i]<<'\n';
    //cout<<"here "<<rt<<'\n';
    while (q--)
    {
        cin>>t;
        vector<int> vl(t);
        for (auto &x:vl) cin>>x;
        for (int i=0; i<t; i++) 
        {
            if (d[vl[i]].size()==1&&!vs[vl[i]]) vs[vl[i]]=1;
            else flip(vl[i]);
        }
        //s.show(1, n, 1);
        if (s.query(1, n, 1)) cout<<-1<<'\n';
        else cout<<s.a[1]+2*s.b[1]+t-2<<'\n';
        for (int i=0; i<t; i++)
        {
            if (d[vl[i]].size()==1&&vs[vl[i]]) vs[vl[i]]=0;
            else flip(vl[i]);
        }
    }
}

• 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