Submission #645678

#	Time	Username	Problem	Language	Result	Execution time	Memory
645678		Pety	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	312 ms	18600 KiB

cleaning

#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 (stderr)

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30