Submission #850557

#	Time	Username	Problem	Language	Result	Execution time	Memory
850557		tvladm2009	Inside information (BOI21_servers)	C++17	57.50 / 100	677 ms	137080 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int N = 480000 + 777;
const int K = 20;
int n;
int k;
vector<pair<int, int>> g[N];
int tab[K][N];
int maxEdge[K][N];
bool inc[K][N];
bool desc[K][N];
int weight[N];
int dep[N];
vector<int> qs[N];
bool active[N];
int sz[N];
int aib[N];

struct T {
  char type;
  int a;
  int b;
  int d;
  int id;
};

vector<T> events;
int sol[2 * N];

int get(int a, int x) {
  for (int k = K - 1; k >= 0; k--) {
    if (x & (1 << k)) {
      a = tab[k][a];
    }
  }
  return a;
}

void build(int a, int p = 0) {
  tab[0][a] = p;
  maxEdge[0][a] = weight[a];
  for (int k = 1; k < K; k++) {
    tab[k][a] = tab[k - 1][tab[k - 1][a]];
    maxEdge[k][a] = max(maxEdge[k - 1][a], maxEdge[k - 1][tab[k - 1][a]]);
  }
  inc[0][a] = 1;
  inc[1][a] = (weight[a] < weight[p]);
  for (int k = 2; k < K; k++) {
    if (inc[k - 1][a] && inc[k - 1][tab[k - 1][a]] && weight[get(a, (1 << (k - 1)) - 1)] < weight[get(a, (1 << (k - 1)))] && weight[get(a, (1 << (k - 1)))] < weight[get(a, (1 << (k - 1)) + 1)]) {
      inc[k][a] = 1;
    }
  }
  desc[0][a] = 1;
  desc[1][a] = (weight[a] > weight[p]);
  for (int k = 2; k < K; k++) {
    if (desc[k - 1][a] && desc[k - 1][tab[k - 1][a]] && weight[get(a, (1 << (k - 1)) - 1)] > weight[get(a, (1 << (k - 1)))] && weight[get(a, (1 << (k - 1)))] > weight[get(a, (1 << (k - 1)) + 1)]) {
      desc[k][a] = 1;
    }
  }
  for (auto &b : g[a]) {
    if (b.first == p) continue;
    dep[b.first] = dep[a] + 1;
    weight[b.first] = b.second;
    build(b.first, a);
  }
}

int get_lca(int x, int y) {
  if (dep[x] < dep[y]) {
    swap(x, y);
  }
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      x = tab[k][x];
    }
  }
  if (x == y) {
    return x;
  }
  for (int k = K - 1; k >= 0; k--) {
    if (tab[k][x] != tab[k][y]) {
      x = tab[k][x];
      y = tab[k][y];
    }
  }
  return tab[0][x];
}

int under(int x, int y) { /// y is ancestor of x
  return get(x, dep[x] - dep[y] - 1);
}

bool isInc(int x, int y) { /// y is ancestor of x
  bool ok = 1;
  int xinit = x;
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      ok &= inc[k][x];
      x = tab[k][x];
      if (x == y) {
        break;
      }
      ok &= (weight[x] > weight[get(xinit, dep[xinit] - dep[x] - 1)]);
    }
  }
  return ok;
}

bool isDesc(int x, int y) { /// y is ancestor of x
  bool ok = 1;
  int xinit = x;
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      ok &= desc[k][x];
      x = tab[k][x];
      if (x == y) {
        break;
      }
      ok &= (weight[x] < weight[get(xinit, dep[xinit] - dep[x] - 1)]);
    }
  }
  return ok;
}

int get_max(int x, int y) {
  int z = get_lca(x, y);
  int ret = 0;
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[z]) {
      ret = max(ret, maxEdge[k][x]);
      x = tab[k][x];
    }
  }
  for (int k = K - 1; k >= 0; k--) {
    if (dep[y] - (1 << k) >= dep[z]) {
      ret = max(ret, maxEdge[k][y]);
      y = tab[k][y];
    }
  }
  return ret;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.second > b.second;
}

void get_sizes(int a, int p = 0) {
  sz[a] = 1;
  for (auto &b : g[a]) {
    if (b.first == p) {
      continue;
    }
    if (active[b.first] == 0) {
      get_sizes(b.first, a);
      sz[a] += sz[b.first];
    }
  }
}

int get_centroid(int a, int limit, int p = 0) {
  for (auto &b : g[a]) {
    if (b.first == p) {
      continue;
    }
    if (active[b.first] == 0 && sz[b.first] >= limit) {
      return get_centroid(b.first, limit, a);
    }
  }
  return a;
}

void add(int i, int x) {
  while (i < N) {
    aib[i] += x;
    i += i & -i;
  }
}

int get(int i) {
  int ret = 0;
  while (i) {
    ret += aib[i];
    i -= i & -i;
  }
  return ret;
}

vector<int> good;

void percolate(int a, int p, int last, int first, bool inc, bool dec) {
  if (dec == true) {
    for (auto &i : qs[a]) {
      sol[i] += get(i);
      if (first <= i) {
        sol[i]++;
      }
    }
  }
  if (inc == true) {
    good.push_back(last);
  }
  for (auto &b : g[a]) {
    if (b.first == p) {
      continue;
    }
    if (!active[b.first]) {
      if (b.second < last) {
        inc = 0;
      }
      if (b.second > last) {
        dec = 0;
      }
      percolate(b.first, a, b.second, first, inc, dec);
    }
  }
}

void decompose(int a, int p = 0) {
  get_sizes(a, a);
  a = get_centroid(a, (sz[a] + 1) / 2, a);
  active[a] = true;
  vector<int> not_active_kids;
  for (auto &b : g[a]) {  
    if (!active[b.first]) {
      percolate(b.first, a, b.second, b.second, 1, 1);
      for (auto &i : good) {
        add(i, 1);
        not_active_kids.push_back(i);
      }
      good.clear();
    }
  }
  for (auto &i : qs[a]) {
    sol[i] += get(i);
  }
  for (auto &i : not_active_kids) {
    add(i, -1);
  }
  for (auto &b : g[a]) {
    if (b.first == p) {
      continue;
    }
    if (!active[b.first]) {
      decompose(b.first, a);
    }
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen ("input", "r", stdin);

  cin >> n >> k;
  for (int i = 1; i <= n + k - 1; i++) {
    T aux;
    cin >> aux.type;
    if (aux.type == 'S') {
      cin >> aux.a >> aux.b;
    } else if (aux.type == 'Q') {
      cin >> aux.a >> aux.d;
    } else if (aux.type == 'C') {
      cin >> aux.d;
    }
    aux.id = i;
    events.push_back(aux);
  }
  for (auto &e : events) {
    if (e.type == 'S') {
      g[e.a].push_back({e.b, e.id});
      g[e.b].push_back({e.a, e.id});
    }
  }
  dep[1] = 1;
  build(1);

  for (auto &e : events) {
    if (e.type == 'S' || e.type == 'C') {
      continue;
    }

    int x = e.a;
    int y = e.d;
    int z = get_lca(x, y);
    int mx = get_max(x, y);
    if (mx > e.id) {
      continue;
    }
    if (z == x) {
      sol[e.id] = isInc(y, x);
      continue;
    }
    if (z == y) {
      sol[e.id] = isDesc(x, y);
      continue;
    }
    if (isInc(y, z) && isDesc(x, z) && weight[under(y, z)] < weight[under(x, z)]) {
      sol[e.id] = 1;
    } else {
      sol[e.id] = 0;
    }
  }

  for (int i = 0; i < n + k - 1; i++) {
    if (events[i].type == 'C') {
      qs[events[i].d].push_back(events[i].id);
    }
  }
  for (int i = 1; i <= n; i++) {
    sort(g[i].begin(), g[i].end(), cmp);
  }
  decompose(1);

  for (auto &e : events) {
    if (e.type == 'Q') {
      cout << (sol[e.id] == 1 ? "yes" : "no") << "\n";
    } else if (e.type == 'C') {
      cout << sol[e.id] + 1 << "\n";
    }
  }
  return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5