Submission #1259881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259881		abdelhakim	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1097 ms	327680 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;
}
vector<pair<ll,ll>> parr;
ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans)
{
  if(node!=par && adj[node].size()==1)
  {
    parr[node]={par,1};
    ans++;
    return 1;
  }
  ll sm=0;
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
    ll val=solve(adj,e,node,ans);
    sm+=val;
    if(val%2)ans++;
    else ans+=2;
  }
  if(adj[node].size()==1 && node==0) sm++;
  parr[node]={par,sm%2};
  if(parr[node].second==0)ans+=2;
  if(node==0 && sm%2)ans=-1;
  return sm;
}
void climb(ll node, 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;
  parr.resize(n);
  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);
  }
  
  while(q--)
  {
    ll cur=n;
    ll d;
    cin>>d;
    vector<vector<ll>> newadj=adj;
    for (int i=0;i<d;i++)
    {
      ll nd;
      cin>>nd;
      nd--;
      newadj[nd].push_back(cur++);
      newadj.push_back({nd});
    }
    ll ans=0;
    solve(newadj,0,0,ans);
    cout << ans << endl;
  }
}

• 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