제출 #1293222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293222		lto5	Tourism (JOI23_tourism)	C++20	34 / 100	5097 ms	25216 KiB

tourism

#include<bits/stdc++.h>

using namespace std;

const int S = 320;
const int L = 18;
const int N = 100005;

int n, m, q;
vector<int> g[N];
int c[N];
int p[N];
int h[N];
int id[N];
int l[N];
int r[N];
int mark[N];
int in[N];
int out[N];
int f[N][L];
int spt[N][L];
int tin[N];
int tout[N];
int s[S];
int blk[N];
int ans[N];
int tree[N];
int tt;

void dfs(int u) {
  tin[u] = ++tt;
  tree[tt] = u;
  for (int i = 0; f[f[u][i]][i]; i++) {
    f[u][i + 1] = f[f[u][i]][i];
  }
  for (int v : g[u]) {
    if (v == p[u]) {
      continue;
    }
    p[v] = u;
    h[v] = h[u] + 1;
    f[v][0] = u;
    dfs(v);
  }
  tout[u] = tt;
}

int lca(int u, int v) {
  if (h[u] < h[v]) {
    swap(u, v);
  }
  while (h[u] > h[v]) {
    u = f[u][__lg(h[u] - h[v])];
  }
  if (u == v) {
    return u;
  }
  for (int i = __lg(h[u]); i >= 0; i--) {
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  }
  return f[u][0];
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("a.inp", "r", stdin);
//  freopen("a", "w", stdout);
#endif // LOCAL
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  for (int i = 1; i <= m; i++) {
    cin >> c[i];
  }
  for (int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    id[i] = i;
  }
  for (int i = 1; i <= m; i++) {
    spt[i][0] = c[i];
  }
  for (int k = 1; (1 << k) <= m; k++) {
    for (int i = 1; i + (1 << k) - 1 <= m; i++) {
      spt[i][k] = lca(spt[i][k - 1], spt[i + (1 << (k - 1))][k - 1]);
    }
  }
  auto lca_range = [&](int l, int r) {
    int k = __lg(r - l + 1);
    return lca(spt[l][k], spt[r - (1 << k) + 1][k]);
  };
  for (int i = 1; i <= q; i++) {
    blk[i] = i / S;
  }
  sort(id + 1, id + q + 1, [&](int i, int j) {
    if (blk[l[i]] != blk[l[j]]) {
      return l[i] < l[j];
    }
    return (blk[l[i]] & 1) ? r[i] < r[j] : r[i] > r[j];
  });
  int cl = 1, cr = 0;
  auto add = [&](int u, int d) {
//    cerr << u << " " << d << endl;
    while (u) {
      s[blk[tin[u]]] -= mark[u] > 0;
//      cerr << "vis " << u << " " << p[u] << endl;
      mark[u] += d;
//      mark[u] = max(mark[u], 0);
      s[blk[tin[u]]] += mark[u] > 0;
      u = p[u];
    }
  };
  auto get_sum = [&](int l, int r) {
    int bl = blk[l];
    int br = blk[r];
    if (bl == br) {
      int ans = 0;
      for (int i = l; i <= r; i++) ans += mark[tree[i]] > 0;
      return ans;
    }
    int ans = 0;
    for (int i = bl + 1; i <= br - 1; i++) {
      ans += s[i];
    }
    for (int i = l; i < (bl + 1) * S; i++) {
      ans += mark[tree[i]] > 0;
    }
    for (int i = br * S; i <= r; i++) {
      ans += mark[tree[i]] > 0;
    }
    return ans;
  };
  for (int i = 1; i <= q; i++) {
    int L = l[id[i]], R = r[id[i]];
    while (cl < L) {
      add(c[cl], -1);
      cl++;
    }
    while (cl > L) {
      cl--;
      add(c[cl], 1);
    }
    while (cr < R) {
      cr++;
      add(c[cr], 1);
    }
    while (cr > R) {
      add(c[cr], -1);
      cr--;
    }
    int lc = lca_range(L, R);
//    cerr << "----\n";
//    for (int u = 1; u <= n; u++) {
//      cerr << u << " " << mark[tree[u]] << endl;
//    }
    ans[id[i]] = get_sum(tin[lc], tout[lc]);
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 41