Submission #850378

#	Time	Username	Problem	Language	Result	Execution time	Memory
850378		tvladm2009	Inside information (BOI21_servers)	C++17	2.50 / 100	143 ms	41432 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int N = 120000 + 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];

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)] < weight[get(a, (1 << k))] && weight[get(a, (1 << k) - 1)] > weight[get(a, (1 << k) - 2)]) {
      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)] > weight[get(a, (1 << k))] && weight[get(a, (1 << k) - 1)] < weight[get(a, (1 << k) - 2)]) {
      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
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) > dep[y]) {
      x = tab[k][x];
    }
  }
  return x;
}

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

bool isDesc(int x, int y) { /// y is ancestor of x
  bool ok = 1;
  for (int k = K - 1; k >= 0; k--) {
    if (dep[x] - (1 << k) >= dep[y]) {
      ok &= desc[k][x];
      x = tab[k][x];
    }
  }
  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;
}

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 (auto &e : events) {
    if (e.type == 'Q') {
      cout << (sol[e.id] == 1 ? "yes" : "no") << "\n";
    }
  }
  return 0;
}

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