oj.uz

Submission #645678

# Submission time Handle Problem Language Result Execution time Memory
645678 2022-09-27T16:06:13 Z Pety Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 312 ms 18600 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;
    map<int, int>mp;
    for (int j = 0; j < nr; j++) {
      cin >> d[j];
      if (G[d[j]].size() > 1) {
        cnt++;
        modify(root, d[j]);
      }
      else {
        int a = ++mp[d[j]];
        if (a > 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";
    mp.clear();
    for (int j = 0; j < nr; j++) 
      if (G[d[j]].size() > 1) {
        modify(root, d[j]);
      }
      else {
        int a = ++mp[d[j]];
        if (a > 1) {
          cnt++;
          modify(root, d[j]);
        }
      }
  }
  
  
  return 0;
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:135:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |         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 Correct 133 ms 4440 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3284 KB Output is correct
2 Correct 68 ms 3680 KB Output is correct
3 Correct 76 ms 11008 KB Output is correct
4 Correct 142 ms 12292 KB Output is correct
5 Correct 174 ms 14588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3796 KB Output is correct
2 Correct 43 ms 3796 KB Output is correct
3 Correct 51 ms 17896 KB Output is correct
4 Correct 127 ms 17056 KB Output is correct
5 Correct 40 ms 15664 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 4816 KB Output is correct
2 Correct 52 ms 4692 KB Output is correct
3 Correct 19 ms 4436 KB Output is correct
4 Correct 14 ms 5124 KB Output is correct
5 Correct 16 ms 4996 KB Output is correct
6 Correct 54 ms 5408 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 7616 KB Output is correct
2 Correct 293 ms 7484 KB Output is correct
3 Correct 221 ms 5956 KB Output is correct
4 Correct 312 ms 8784 KB Output is correct
5 Correct 294 ms 8752 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 10852 KB Output is correct
2 Correct 151 ms 13096 KB Output is correct
3 Correct 183 ms 12876 KB Output is correct
4 Correct 177 ms 13384 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 133 ms 4440 KB Output is correct
3 Correct 72 ms 3284 KB Output is correct
4 Correct 68 ms 3680 KB Output is correct
5 Correct 76 ms 11008 KB Output is correct
6 Correct 142 ms 12292 KB Output is correct
7 Correct 174 ms 14588 KB Output is correct
8 Correct 43 ms 3796 KB Output is correct
9 Correct 43 ms 3796 KB Output is correct
10 Correct 51 ms 17896 KB Output is correct
11 Correct 127 ms 17056 KB Output is correct
12 Correct 40 ms 15664 KB Output is correct
13 Correct 109 ms 4816 KB Output is correct
14 Correct 52 ms 4692 KB Output is correct
15 Correct 19 ms 4436 KB Output is correct
16 Correct 14 ms 5124 KB Output is correct
17 Correct 16 ms 4996 KB Output is correct
18 Correct 54 ms 5408 KB Output is correct
19 Correct 219 ms 7616 KB Output is correct
20 Correct 293 ms 7484 KB Output is correct
21 Correct 221 ms 5956 KB Output is correct
22 Correct 312 ms 8784 KB Output is correct
23 Correct 294 ms 8752 KB Output is correct
24 Correct 271 ms 10852 KB Output is correct
25 Correct 151 ms 13096 KB Output is correct
26 Correct 183 ms 12876 KB Output is correct
27 Correct 177 ms 13384 KB Output is correct
28 Correct 218 ms 8444 KB Output is correct
29 Correct 216 ms 14476 KB Output is correct
30 Correct 206 ms 14552 KB Output is correct
31 Correct 126 ms 18600 KB Output is correct
32 Correct 301 ms 8784 KB Output is correct
33 Correct 176 ms 13792 KB Output is correct
34 Correct 203 ms 14128 KB Output is correct
35 Correct 175 ms 15096 KB Output is correct