Submission #1270529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270529		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	413 ms	26696 KiB

cleaning

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
vector<int>dsk[200005];
int d;pair<int,int>p[200005];
int dem=n;
int m1[200005],m2[200005];
int ans=0;
void dfs(int u,int par){
   int dl=0;
//   cout<<u;
   vector<int>vec;
   for(int v:dsk[u]){
      if(v==par)continue;
//      dl=1;
//      cout<<v;
      dfs(v,u);
//
      if(dsk[v].size()==1){
         vec.push_back(1);
//
      }
      else{
         if(m1[v])vec.push_back(m1[v]+1);
         if(m2[v])vec.push_back(m2[v]+1);
      }
//
   }
   while(vec.size()>2){
      ans+=vec.back();
//      cout<<vec.back();

      vec.pop_back();
      ans+=vec.back();
      vec.pop_back();
   }
   if(vec.size()>0)m1[u]=vec[0];
   if(vec.size()==2)m2[u]=vec[1];

   if(u==par){
      ans+=m1[u];
      ans+=m2[u];

   }

}

void sub1(){
//   cout<<q;
   while(q--){
      dem=n;
      cin>>d;
      for(int i=1;i<=d;++i){
         int u;cin>>u;
//         if(q==2)cout<<dem;
         dem++;
         int v=dem;
         dsk[u].push_back(dem);
         dsk[dem].push_back(u);
         p[i]={u,v};
      }
      int dl=0;
      for(int i=1;i<=dem;++i){
         if(dsk[i].size()==1)dl++;
         m1[i]=0;m2[i]=0;
      }
      if(dl%2){cout<<"-1\n";
         for(int i=d;i>0;--i){
            int u=p[i].first,v=p[i].second;
            dsk[u].pop_back();
            dsk[v].pop_back();
//            cout<<u<<v;
            dem--;
         }
         continue;
      }
      int vl=0;

//      cout<<dsk[8][0];

      for(int i=1;i<=n;++i)if(  dsk[i].size()>1){
         ans=0;
         dfs(i,i);
//         vl=1;
//         cout<<dl;
         break;
      }
      cout<<ans<<"\n";
      for(int i=d;i>0;--i){
            int u=p[i].first,v=p[i].second;
            dsk[u].pop_back();
            dsk[v].pop_back();
            dem--;
      }
   }


}

int32_t main(){
   ios_base::sync_with_stdio(false);cin.tie(NULL);
  // freopen("crt.inp","r",stdin);freopen("crt.out","w",stdout);
   cin>>n>>q;
   for(int i=1;i<n;++i){
      int u,v;
      cin>>u>>v;
      dsk[u].push_back(v);
      dsk[v].push_back(u);
   }
//   cout<<q;
//   dfs(1,0);
   if((n<=20000 and q<=300) or q==1){sub1();return 0;}
   int dl=0;
   for(int i=1;i<=n;++i)if(dsk[i].size()==1)dl++;
   if(dl%2==0){
      ans=0;
      for(int i=1;i<=n;++i)if(dsk[i].size()>1){dfs(i,i);break;}
      while(q--){
         int d;cin>>d;cin>>d;
         if(dsk[d].size()==1)cout<<ans+1;
         else cout<<-1;
         cout<<"\n";
      }

   }




}

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