oj.uz

Submission #645675

# Submission time Handle Problem Language Result Execution time Memory
645675 2022-09-27T16:02:22 Z Pety Spring cleaning (CEOI20_cleaning) C++14
26 / 100
 314 ms 19060 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int N = 1e5+2;

int n, q, head[N], par[N], sz[N], best_child[N], poz[N], lvl[N];
int aint[4 * N], lazy[4 * N];
vector<int>G[N];

void dfs1 (int nod, int p) {
  par[nod] = p;
  sz[nod] = 1;
  lvl[nod] = lvl[p] + 1;
  for (auto it : G[nod]) {
    if (it != p) {
      dfs1(it, nod);
      sz[nod] += sz[it];
      if (best_child[nod] == 0 || sz[best_child[nod]] < sz[it])
        best_child[nod] = it;
    }
  }
}

int t;

void dfs2 (int nod, int p, int h) {
  head[nod] = h;
  poz[nod] = ++t;
  if (best_child[nod])
    dfs2(best_child[nod], nod, h);
  for (auto it : G[nod])
    if (it != p && it != best_child[nod])
      dfs2(it, nod, it);
}

void push (int nod, int st, int dr) {
  if (lazy[nod] != 0) {
    aint[nod] = dr - st + 1 - aint[nod];
    if(st != dr) {
      lazy[2 * nod] ^= lazy[nod];
      lazy[2 * nod + 1] ^= lazy[nod];
    }
    lazy[nod] = 0;
  }
}

void update (int nod, int st, int dr, int a, int b) {
  push(nod, st, dr);
  if (a > b || b < st || a > dr)
    return;
  if (a <= st && dr <= b) {
    aint[nod] = dr - st + 1 - aint[nod];
    if (st != dr) {
      lazy[2 * nod] ^= 1;
      lazy[2 * nod + 1] ^= 1;
    }
    return;
  }
  int mid = (st + dr) / 2;
  update(2 * nod, st, mid, a, b);
  update(2 * nod + 1, mid + 1, dr, a, b);
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void modify (int a, int b) {
  while (head[a] != head[b]) {
    if (lvl[head[a]] < lvl[head[b]])
      swap(a, b);
    update(1, 1, n, poz[head[a]], poz[a]);
    a = par[head[a]];
  }
  if (lvl[a] > lvl[b])
    swap(a, b);
  update(1, 1, n, poz[a], poz[b]);
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  int root;
  for (int i = 1; i <= n; i++)
    if (G[i].size() > 1)
      root = i;
  dfs1(root, 0);
  dfs2(root, 0, root);
  int frunze = 0;
  for (int i = 1; i <= n; i++) {
    if (G[i].size() == 1) {
      modify(root, i);
      frunze++;
    }
  }
  update(1, 1, n, 1, n);
  for (int i = 1; i <= q; i++) {
    int nr;
    cin >> nr;
    vector<int>d(nr);
    int cnt = 0;
    for (int j = 0; j < nr; j++) {
      cin >> d[j];
      if (G[d[j]].size() > 1) {
        cnt++;
        modify(root, d[j]);
      }
    }
    if ((frunze + cnt) % 2 == 0) {
      push(1, 1, n);
      cout << (n + nr) + aint[1] - 2 << "\n";
    }
    else 
      cout << "-1\n";
    for (int j = 0; j < nr; j++) 
      if (G[d[j]].size() > 1) {
        modify(root, d[j]);
      }
  }
  
  
  return 0;
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:126:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |         modify(root, d[j]);
      |         ~~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 109 ms 5092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4188 KB Output is correct
2 Correct 44 ms 4180 KB Output is correct
3 Correct 44 ms 19060 KB Output is correct
4 Correct 111 ms 18668 KB Output is correct
5 Correct 45 ms 16716 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 5328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 8744 KB Output is correct
2 Incorrect 314 ms 8604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12716 KB Output is correct
2 Correct 138 ms 14968 KB Output is correct
3 Correct 174 ms 14896 KB Output is correct
4 Correct 194 ms 15320 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 109 ms 5092 KB Output isn't correct
3 Halted 0 ms 0 KB -