Submission #1260422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260422		abdelhakim	Spring cleaning (CEOI20_cleaning)	C++20	9 / 100	1095 ms	22224 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<ll> value;
vector<ll> in;
vector<ll> out;
ll maxn=1e5;
vector<ll> tree(4*maxn+3);
void update(ll node, ll l, ll r, ll pos, ll val)
{
  if(pos > r || pos < l)
  {
    return;
  }
  if(l==r)
  {
    tree[node]=val;
    return;
  }
  ll mid=(l+r)>>1;
  update(node*2+1,l,mid,pos,val);
  update(node*2+2,mid+1,r,pos,val);
  tree[node]=tree[node*2+1]+tree[node*2+2];
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
  if(max(l,x) > min(r,y))
  {
    return 0;
  }
  if(l==r)
  {
    return tree[node];
  }
  ll mid=(l+r)>>1;
  return query(node*2+1,l,mid,x,y)+query(node*2+2,mid+1,r,x,y);
}
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 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);
  value.resize(n);
  in.resize(n);
  out.resize(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);
  ll time=0;
  dfs(0,0,0,adj,parr,time);
  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 (auto &&e : v)
      {
        update(0,0,n-1,in[e],1);
      }
      for (auto &&e : v)
      {
        ll vl=query(0,0,n-1,in[e]+1,out[e]);
        if(vl%2)
        {
          ans-=value[e];
        }
        else
        {
          ans+=value[e];
        }
      }
      cout << ans << endl;
      for (auto &&e : v)
      {
        update(0,0,n-1,in[e],0);
      }
    }
  }
}

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