Submission #466499

#	Time	Username	Problem	Language	Result	Execution time	Memory
466499		ivan_tudor	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	364 ms	20384 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
struct ainthelp{
  int nr1, nr2;
  bool swp;
};
const int N = 1e5 + 5;
vector<int> gr[N];
int sum[N];
int aux[N];
bool isleaf[N];
int sz[N];
int id[N];
int head[N];
int par[N];
ainthelp aint[4*N];
int n, nrleaf;
void propag(int nod, int l, int r){
  if(aint[nod].swp){
    aint[nod].swp = false;
    swap(aint[nod].nr1, aint[nod].nr2);
    if(l != r){
      aint[2*nod].swp ^=true;
      aint[2*nod + 1].swp ^= true;
    }
  }
}
void build(int nod, int l, int r){
  if(l == r){
    if(aux[l] == 0)
      return;
    if(aux[l] %2 == 0)
      aint[nod].nr2 = 1;
    else
      aint[nod].nr1 = 1;
    return;
  }
  int mid = (l + r)/2;
  build(2*nod, l, mid);
  build(2*nod + 1, mid + 1, r);
  aint[nod] = {aint[2*nod].nr1 + aint[2*nod + 1].nr1, aint[2*nod].nr2 + aint[2*nod + 1].nr2, false};
}
void update(int nod, int l, int r, int ul, int ur){
  propag(nod, l, r);
  if(l > ur || r < ul)
    return;
  if(ul <= l && r <= ur){
    aint[nod].swp ^= true;
    propag(nod, l, r);
    return;
  }
  int mid = (l + r)/2;
  update(2*nod, l, mid, ul, ur);
  update(2*nod + 1, mid + 1, r, ul, ur);
  aint[nod] = {aint[2*nod].nr1 + aint[2*nod + 1].nr1, aint[2*nod].nr2 + aint[2*nod + 1].nr2, false};
}
void buildsum(int nod, int dad){
  bool ok = false;
  sz[nod] = 1;
  for(auto x:gr[nod]){
    if(x != dad){
      buildsum(x, nod);
      ok = true;
      sum[nod] += sum[x];
      sz[nod] += sz[x];
    }
  }
  if(ok == false){
    sum[nod] = 1;
    isleaf[nod] = true;
    nrleaf++;
  }
  if(dad == 0)
    sum[nod] = 0;
}
void build_hld(int nod, int dad, int hd, int &cnt){
  id[nod] = ++cnt;
  aux[cnt] = sum[nod];
  head[nod] = hd;
  par[nod] = dad;

  int vmson = 0, mson = -1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    if(sz[x] > vmson){
      vmson = sz[x];
      mson = x;
    }
  }
  if(mson == -1)
    return;
  build_hld(mson, nod, hd, cnt);
  for(auto x:gr[nod]){
    if(x == dad || x == mson)
      continue;
    build_hld(x, nod, x, cnt);
  }

}
int addlf[N];
void update_hld(int nod){
  while(nod != 0){
    int othnod = head[nod];
    update(1, 1, n, id[othnod], id[nod]);
    nod = par[othnod];
  }

}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int q;
  cin>>n>>q;
  for(int i = 1; i < n; i++){
    int a, b;
    cin>>a>>b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  int root = 1;
  while(gr[root].size() == 1)
    root++;
  buildsum(root, 0);
  int cnt = 0;
  build_hld(root, 0, root, cnt);
  build(1, 1, n);
  for(int i = 1; i <=q; i++){
    vector<int> nl;
    int d;
    cin>>d;
    for(int j = 1; j <=d; j++){
      int x;
      cin>>x;
      nl.push_back(x);
    }
    for(auto x:nl){
      if(isleaf[x] == true && addlf[x] == 0){
        addlf[x]++;
        continue;
      }
      nrleaf++;
      update_hld(x);
      addlf[x]++;
    }
    propag(1, 1, n);
    int ans = aint[1].nr1 + 2 * aint[1].nr2;
    if(nrleaf%2 == 0)
      cout<<ans + d<<"\n";
    else
      cout<<"-1\n";
    for(auto x:nl){
      if(isleaf[x] == true && addlf[x] == 1){
        addlf[x]--;
        continue;
      }
      nrleaf--;
      update_hld(x);
      addlf[x]--;
    }
  }
  return 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