Submission #342852

#	Time	Username	Problem	Language	Result	Execution time	Memory
342852		leinad2	Spring cleaning (CEOI20_cleaning)	C++17	0 / 100	268 ms	13676 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
const int MX=100010;
int sz[MX], dep[MX], par[MX], top[MX], in[MX], n, q, i, j, k, a, b, ans, r, cnt, seg[4*MX], lazy[4*MX], A[MX], sz2[MX], x;
vector<int>w[MX], adj[MX];
void busy(int id, int s, int e, int m)
{
    if(lazy[id])
    {
        seg[id*2]=(m-s+1)-seg[id*2];
        seg[id*2+1]=(e-m)-seg[id*2+1];
        lazy[id*2]^=1;
        lazy[id*2+1]^=1;
    }
}
void update(int id, int s, int e, int l, int r)
{
    if(e<l||r<s)return;
    if(l<=s&&e<=r)
    {
        seg[id]=(e-s+1)-seg[id];
        lazy[id]^=1;
        return;
    }
    int m=s+e>>1;
    busy(id, s, e, m);
    update(id*2, s, m, l, r);
    update(id*2, m+1, e, l, r);
    seg[id]=seg[id*2]+seg[id*2+1];
}
void dfs(int v, int P)
{
    par[v]=P;
    for(int i=0;i<w[v].size();i++)
    {
        int p=w[v][i];
        if(p==P)continue;
        adj[v].push_back(p);
        dfs(p, v);
    }
}
void dfs1(int v, int depth)
{
    dep[v]=depth;
    sz[v]=1;
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i];
        dfs1(p, depth+1);
        sz[v]+=sz[p];
        if(sz[p]>sz[adj[v][0]])
        {
            swap(adj[v][i], adj[v][0]);
        }
    }
}
void dfs2(int v)
{
    in[v]=++cnt;
    if(adj[v].size()==0)
    {
        sz2[v]=1;
        return;
    }
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i];
        top[p]=(i==0?top[v]:p);
        dfs2(p);
        sz2[v]+=sz2[p];
    }
    sz2[v]%=2;
}
void upd(int a, int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]])swap(a, b);
        update(1, 1, n, in[top[a]], in[a]);
        a=par[top[a]];
    }
    if(dep[a]>dep[b])swap(a, b);
    update(1, 1, n, in[a], in[b]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(cin>>n>>q;++i<n;)
    {
        cin>>a>>b;
        w[a].push_back(b);
        w[b].push_back(a);
    }
    ans=n-2;
    for(i=0;i++<n;)
    {
        if(w[i].size()>1)
        {
            r=i;
            break;
        }
    }
    top[r]=r;
    dfs(r, 0);
    dfs1(r, 1);
    dfs2(r);
    for(i=0;i++<n;)
    {
        A[i]=adj[i].size();
        if(sz2[i]==0)ans++;
        else
        {
            update(1, 1, n, in[i], in[i]);
        }
    }
    x=sz2[r];
    while(q--)
    {
        vector<int>v;
        cin>>a;
        while(a--)
        {
            cin>>b;
            v.push_back(b);
            A[b]++;
            ans++;
            if(A[b]==1)continue;
            ans-=seg[1];
            upd(r, b);
            ans+=seg[1];
            x=1-x;
        }
        if(x==0)cout<<ans<<"\n";
        else cout<<"-1\n";
        while(v.size())
        {
            b=v.back();
            v.pop_back();
            A[b]--;
            ans--;
            if(A[b]==0)continue;
            ans-=seg[1];
            upd(r, b);
            ans+=seg[1];
            x=1-x;
        }
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'void update(int, int, int, int, int)':
cleaning.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int m=s+e>>1;
      |           ~^~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<w[v].size();i++)
      |                 ~^~~~~~~~~~~~
cleaning.cpp: In function 'void dfs1(int, int)':
cleaning.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs2(int)':
cleaning.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30