oj.uz

Submission #466499

# Submission time Handle Problem Language Result Execution time Memory
466499 2021-08-19T13:20:25 Z ivan_tudor Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 364 ms 20384 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 161 ms 5460 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 3916 KB Output is correct
2 Correct 85 ms 3916 KB Output is correct
3 Correct 39 ms 12884 KB Output is correct
4 Correct 96 ms 11768 KB Output is correct
5 Correct 100 ms 13756 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4560 KB Output is correct
2 Correct 71 ms 4560 KB Output is correct
3 Correct 63 ms 20384 KB Output is correct
4 Correct 166 ms 20056 KB Output is correct
5 Correct 57 ms 19012 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6000 KB Output is correct
2 Correct 62 ms 5076 KB Output is correct
3 Correct 14 ms 4812 KB Output is correct
4 Correct 13 ms 5492 KB Output is correct
5 Correct 16 ms 5628 KB Output is correct
6 Correct 75 ms 5552 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 9620 KB Output is correct
2 Correct 351 ms 9552 KB Output is correct
3 Correct 275 ms 6340 KB Output is correct
4 Correct 364 ms 9532 KB Output is correct
5 Correct 328 ms 9412 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 14160 KB Output is correct
2 Correct 151 ms 16904 KB Output is correct
3 Correct 225 ms 17012 KB Output is correct
4 Correct 216 ms 16324 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 161 ms 5460 KB Output is correct
3 Correct 90 ms 3916 KB Output is correct
4 Correct 85 ms 3916 KB Output is correct
5 Correct 39 ms 12884 KB Output is correct
6 Correct 96 ms 11768 KB Output is correct
7 Correct 100 ms 13756 KB Output is correct
8 Correct 69 ms 4560 KB Output is correct
9 Correct 71 ms 4560 KB Output is correct
10 Correct 63 ms 20384 KB Output is correct
11 Correct 166 ms 20056 KB Output is correct
12 Correct 57 ms 19012 KB Output is correct
13 Correct 112 ms 6000 KB Output is correct
14 Correct 62 ms 5076 KB Output is correct
15 Correct 14 ms 4812 KB Output is correct
16 Correct 13 ms 5492 KB Output is correct
17 Correct 16 ms 5628 KB Output is correct
18 Correct 75 ms 5552 KB Output is correct
19 Correct 217 ms 9620 KB Output is correct
20 Correct 351 ms 9552 KB Output is correct
21 Correct 275 ms 6340 KB Output is correct
22 Correct 364 ms 9532 KB Output is correct
23 Correct 328 ms 9412 KB Output is correct
24 Correct 295 ms 14160 KB Output is correct
25 Correct 151 ms 16904 KB Output is correct
26 Correct 225 ms 17012 KB Output is correct
27 Correct 216 ms 16324 KB Output is correct
28 Correct 228 ms 9184 KB Output is correct
29 Correct 218 ms 16708 KB Output is correct
30 Correct 105 ms 13992 KB Output is correct
31 Correct 176 ms 20028 KB Output is correct
32 Correct 344 ms 9520 KB Output is correct
33 Correct 206 ms 14604 KB Output is correct
34 Correct 264 ms 16716 KB Output is correct
35 Correct 241 ms 16612 KB Output is correct