제출 #498034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498034		andrei_boaca	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	329 ms	50148 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,q,parent[100005],root,niv[100005],leaves[100005],nr[100005],topar[100005],where[100005],poz[100005],ans;
vector<int> vals;
int pathpar[100005];
set<int> used;
int nrleaves,nrpaths;
bool isheavy[100005];
vector<pii> muchii[100005];
vector<int> path[100005];
vector<vector<int>> arb,toprop,good;
void prop(int index,int nod,int st,int dr)
{
    int mij=(st+dr)/2;
    int lg=mij-st+1;
    int nr=arb[index][nod*2];
    arb[index][nod*2]=lg-nr;
    toprop[index][nod*2]++;
    toprop[index][nod*2]%=2;

    lg=dr-mij;
    nr=arb[index][nod*2+1];
    arb[index][nod*2+1]=lg-nr;
    toprop[index][nod*2+1]++;
    toprop[index][nod*2+1]%=2;
}
void update(int index,int nod,int st,int dr,int a,int b, int val)
{
    if(st!=dr&&toprop[index][nod]==1)
        prop(index,nod,st,dr);
    toprop[index][nod]=0;
    if(st>=a&&dr<=b)
    {
        int lg=dr-st+1;
        int nr=arb[index][nod];
        arb[index][nod]=lg-nr;
        ans-=(nr*1+(lg-nr)*2);
        ans+=(lg-nr)*1+nr*2;
        toprop[index][nod]++;
        toprop[index][nod]%=2;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(index,nod*2,st,mij,a,b,val);
    if(b>mij)
        update(index,nod*2+1,mij+1,dr,a,b,val);
    arb[index][nod]=(arb[index][nod*2]+arb[index][nod*2+1]);
}
void dfs(int nod)
{
    if(niv[nod]==0)
        niv[nod]=1;
    nr[nod]=1;
    if(muchii[nod].size()==1)
    {
        leaves[nod]=1;
        nr[nod]=1;
        nrleaves++;
        return;
    }
    for(auto i:muchii[nod])
        if(i.first!=parent[nod])
        {
            topar[i.first]=i.second;
            niv[i.first]=niv[nod]+1;
            parent[i.first]=nod;
            dfs(i.first);
            nr[nod]+=nr[i.first];
            leaves[nod]+=leaves[i.first];
        }
    int maxim=0,index=0;
    for(auto i:muchii[nod])
        if(i.first!=parent[nod])
            if(nr[i.first]>maxim)
            {
                maxim=nr[i.first];
                index=i.second;
            }
    isheavy[index]=1;
}
void build_path()
{
    for(int i=1;i<=n;i++)
    {
        bool found=0;
        for(auto j:muchii[i])
            if(j.first!=parent[i])
                if(isheavy[j.second])
                    found=1;
        if(!found)
        {
            nrpaths++;
            path[nrpaths].push_back(0);
            path[nrpaths].push_back(i);
            where[i]=nrpaths;
            poz[i]=1;
            int nod=i;
            while(isheavy[topar[nod]])
            {
                nod=parent[nod];
                path[nrpaths].push_back(nod);
                poz[nod]=path[nrpaths].size()-1;
                where[nod]=nrpaths;
            }
            int last=path[nrpaths][path[nrpaths].size()-1];
            pathpar[nrpaths]=parent[last];
        }
    }
    arb.resize(nrpaths+1);
    toprop.resize(nrpaths+1);
    good.resize(nrpaths+1);
    for(int i=1;i<=nrpaths;i++)
    {
        int lg=path[i].size();
        arb[i].resize(5*(lg+1));
        toprop[i].resize(5*(lg+1));
        for(int j=1;j<=5*lg;j++)
            arb[i][j]=toprop[i][j]=0;
        good[i].resize(5*(lg+1));
        for(int j=1;j<lg;j++)
        {
            int nod=path[i][j];
            if(leaves[nod]%2==1)
                update(i,1,1,lg-1,j,j,1);
        }
    }
}
void plsupdate(int nod)
{
    while(nod>0)
    {
        int p=poz[nod];
        int index=where[nod];
        int lg=path[index].size();
        lg--;
        update(index,1,1,lg,p,lg,1);
        int last=path[index][path[index].size()-1];
        nod=pathpar[index];
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>q;
    ans=2*n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
    }
    for(int i=1;i<=n;i++)
        if(muchii[i].size()>1)
        {
            root=i;
            break;
        }
    dfs(root);
    build_path();
    //cout<<ans-(nrpaths%2==0?2:1)<<'\n';
    while(q--)
    {
        int m;
        cin>>m;
        used.clear();
        vals.clear();
        for(int i=1;i<=m;i++)
        {
            int nod;
            cin>>nod;
            bool ok=0;
            if(nod==3&&ans>12)
                ok=1;
            vals.push_back(nod);
            ans++;
            bool fnd=0;
            if(muchii[nod].size()==1&&used.find(nod)==used.end())
                fnd=1;
            else
            {
                plsupdate(nod);
                nrleaves++;
            }
            used.insert(nod);
        }
        if(nrleaves%2==1)
            cout<<-1<<'\n';
        else
            cout<<ans-2<<'\n';
        used.clear();
        for(int nod:vals)
        {
            ans--;
            bool fnd=0;
            if(muchii[nod].size()==1&&used.find(nod)==used.end())
                fnd=1;
            else
            {
                plsupdate(nod);
                nrleaves--;
            }
            used.insert(nod);
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cleaning.cpp: In function 'void plsupdate(int)':
cleaning.cpp:140:13: warning: unused variable 'last' [-Wunused-variable]
  140 |         int last=path[index][path[index].size()-1];
      |             ^~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:175:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  175 |             bool ok=0;
      |                  ^~
cleaning.cpp:180:18: warning: variable 'fnd' set but not used [-Wunused-but-set-variable]
  180 |             bool fnd=0;
      |                  ^~~
cleaning.cpp:198:18: warning: variable 'fnd' set but not used [-Wunused-but-set-variable]
  198 |             bool fnd=0;
      |                  ^~~

• 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