Submission #1262173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262173		abdelhakim	Spring cleaning (CEOI20_cleaning)	C++20	28 / 100	1094 ms	16760 KiB

cleaning

// #include <bits/stdc++.h>
// #define ll long long
// #define dbg(x) cerr << #x << ' ' <<  x << endl; 
// #define inf 1e18
// using namespace std;

// void printvec(vector<ll>& vec)
// {
//   for (auto &&e : vec)
//   {
//     cout << e << ' ';
//   }
//   cout << endl;
// }
// const int maxn = 1e5;
// int value[maxn];
// int in[maxn];
// int out[maxn];
// int arr2[maxn];
// const int lg=18;
// int up[maxn][lg];

// ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans,vector<pair<ll,ll>>& parr)
// {
//   if(node!=par && adj[node].size()==1)
//   {
//     parr[node]={par,1};
//     if(node!=0)
//     {
//       if(parr[node].second==0) ans+=2;
//       else ans++;
//     }
//     return 1;
//   }
//   ll sm=0;
//   for (auto &&e : adj[node])
//   {
//     if(e==par)continue;
//     ll val=solve(adj,e,node,ans,parr);
//     sm+=val;
//   }
//   if(adj[node].size()==1 && node==0) sm++;
//   parr[node]={par,sm%2};
//   if(node!=0)
//   {
//     if(parr[node].second==0) ans+=2;
//     else ans++;
//   }
//   return sm;
// }
// void dfs(ll node, ll par, ll cur,vector<vector<ll>>& adj, vector<pair<ll,ll>>& parr, ll& time)
// {
//   in[node]=time;
//   if(node!=0)
//   {
//     if(parr[node].second)
//     {
//       cur++;
//     }
//     else cur--;
//   }
//   value[node]=cur;
//   for (auto &&e : adj[node])
//   {
//     if(e==par) continue;
//     time++;
//     dfs(e,node,cur,adj,parr,time); 
//   }
//   out[node] = time;
// }
// void gadup(ll n, vector<pair<ll,ll>>& parr)
// {
//   for (int i=0;i<n;i++)
//   {
//     for (int j=0;j<lg;j++)
//     {
//       if(j==0)
//       {
//         up[i][j]=parr[i].first;
//       }
//       else
//       {
//         up[i][j]=up[up[i][j-1]][j-1];
//       }
//     }
//   }
// }
// bool islca(ll a, ll b)
// {
//   if(in[a] <= in[b] && in[b] <= out[a]) return true;
//   return false;
// }
// ll lca(ll u, ll v)
// {
//   if(islca(u,v)) return u;
//   if(islca(v,u)) return v;
//   for (int j=lg-1;j>=0;j--)
//   {
//     if(!(islca(up[u][j],v)))
//     {
//       u=up[u][j];
//     }
//   }
//   u=up[u][0];
//   return u;
// }
// ll dfs2(ll& ans, ll node, ll par, vector<vector<ll>>& adj)
// {
//   if(node!=0 && adj[node].size()==1) return arr2[node];
//   ll val=arr2[node];
//   for (auto &&e : adj[node])
//   {
//     if(e==par) continue;
//     ll qry=dfs2(ans,e,node,adj);
//     val+=qry;
//     if(qry%2)
//     {
//       ans+=value[e]-value[node];
//     }
//   }
//   return val;
// }
// int main()
// {
//   cin.tie(0);
//   ios_base::sync_with_stdio(false);
//   ll n, q;
//   cin>>n>>q;
//   for (int i=0;i<maxn;i++)
//   {
//     arr2[i]=0;
//   }
//   vector<vector<ll>> adj(n);
//   value[0]=0;
//   for (int i=0;i<n-1;i++)
//   {
//     ll u, v;
//     cin>>u>>v;
//     u--;v--;
//     adj[u].push_back(v);
//     adj[v].push_back(u);
//   }
//   ll old=0;
//   ll leaves=0;
//   for (int i=0;i<n;i++)
//   {
//     leaves+=adj[i].size()==1;
//   }
//   vector<pair<ll,ll>> parr(n);
//   solve(adj,0,0,old,parr);
//   ll time=0;
//   dfs(0,0,0,adj,parr,time);
//   gadup(n,parr);
//   vector<vector<ll>> adj2(n);
//   while(q--)
//   {
//     ll d;
//     cin>>d;
//     vector<ll> v;
//     vector<ll> arr;
//     ll ans=old;
//     ll val=leaves;
//     for (int i=0;i<d;i++)
//     {
//       ll nd;
//       cin>>nd;
//       nd--;
//       arr.push_back(nd);
//     }
//     auto comp=[&](ll a, ll b){return in[a]<in[b];};
//     sort(arr.begin(), arr.end(),comp);
//     ll cur=0;
//     for (int i=0;i<d;i++)
//     {
//       cur++;
//       if(i==d-1 || arr[i+1]!=arr[i])
//       {
//         if(adj[arr[i]].size()==1)
//         {
//           cur--;
//         }
//         if(cur%2) v.push_back(arr[i]);
//         cur=0;
//       }
//     }
//     val+=v.size();
//     if(val%2) cout<<-1<<endl;
//     else
//     {
//       ans+=d;
//       vector<ll> v2;
//       for (auto &&e : v)
//       {
//         arr2[e]=1;
//         v2.push_back(e);
//       }
      
//       ll sz=v.size();
//       for (int i=0;i<sz-1;i++)
//       {
//         v.push_back(lca(v[i],v[i+1]));
//       }
//       v.push_back(0);
//       sort(v.begin(), v.end(),comp);
//       v.erase(unique(v.begin(),v.end()),v.end());
//       for (int i=0;i<v.size()-1;i++)
//       {
//         ll l=lca(v[i],v[i+1]);
//         adj2[v[i+1]].push_back(l);
//         adj2[l].push_back(v[i+1]);
//       }
//       dfs2(ans,0,0,adj2);
//       cout << ans << endl;
//       for (auto &&e : v)
//       {
//         adj2[e].clear();
//       }
//       for (auto &&e : v2)
//       {
//         arr2[e]=0;
//       }
      
//     }
//   }
// }

#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr << #x << ' ' <<  x << endl; 
#define inf 1e18
using namespace std;

void printvec(vector<ll>& vec)
{
  for (auto &&e : vec)
  {
    cout << e << ' ';
  }
  cout << endl;
}
ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans,vector<pair<ll,ll>>& parr)
{
  if(node!=par && adj[node].size()==1)
  {
    parr[node]={par,1};
    if(node!=0)
    {
      if(parr[node].second==0) ans+=2;
      else ans++;
    }
    return 1;
  }
  ll sm=0;
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
    ll val=solve(adj,e,node,ans,parr);
    sm+=val;
  }
  if(adj[node].size()==1 && node==0) sm++;
  // if(node==0 && sm%2) ans=-1;
  parr[node]={par,sm%2};
  if(node!=0)
  {
    if(parr[node].second==0) ans+=2;
    else ans++;
  }
  return sm;
}
void tl3(ll node, vector<pair<ll,ll>>& parr, ll& ans)
{
  while(node!=0)
  {
    if(parr[node].second==0)ans--;
    else ans++;
    parr[node].second^=1;
    node=parr[node].first;
  }
}
int main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll n, q;
  cin>>n>>q;
  vector<vector<ll>> adj(n);
  for (int i=0;i<n-1;i++)
  {
    ll u, v;
    cin>>u>>v;
    u--;v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  ll old=0;
  ll leaves=0;
  for (int i=0;i<n;i++)
  {
    leaves+=adj[i].size()==1;
  }
  vector<pair<ll,ll>> parr(n);
  solve(adj,0,0,old,parr);
  while(q--)
  {
    ll d;
    cin>>d;
    vector<ll> v;
    vector<ll> arr;
    ll ans=old;
    ll val=leaves;
    for (int i=0;i<d;i++)
    {
      ll nd;
      cin>>nd;
      nd--;
      arr.push_back(nd);
    }
    sort(arr.begin(), arr.end());
    ll cur=0;
    for (int i=0;i<d;i++)
    {
      cur++;
      if(i==d-1 || arr[i+1]!=arr[i])
      {
        if(adj[arr[i]].size()==1)
        {
          cur--;
        }
        if(cur%2) v.push_back(arr[i]);
        cur=0;
      }
    }
    val+=v.size();
    if(val%2) cout<<-1<<endl;
    else
    {
      ans+=d;
      for (int i=0;i<v.size();i++)
    {
      ll nd=v[i];
      tl3(nd,parr,ans);
    }
    cout << ans << endl;
    for (auto &&e : v)
    {
      tl3(e,parr,ans);
    }
  }
  }
}

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