Submission #781945

#	Time	Username	Problem	Language	Result	Execution time	Memory
781945		peijar	Tourism (JOI23_tourism)	C++17	100 / 100	3038 ms	107288 KiB

tourism

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

template <class T> struct RMQ {
  vector<vector<T>> jmp;
  RMQ(const vector<T> &V) : jmp(1, V) {
    for (int pw = 1, k = 1; pw * 2 <= (int)V.size(); pw *= 2, ++k) {
      jmp.emplace_back((int)V.size() - pw * 2 + 1);
      for (int j = 0; j < (int)jmp[k].size(); ++j)
        jmp[k][j] = max(jmp[k - 1][j], jmp[k - 1][j + pw]);
    }
  }
  T query(int a, int b) { // [a, b)
    assert(a < b);
    int dep = 31 - __builtin_clz(b - a);
    return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
  }
};

const int MAXN = 4e5 + 1;
const int MAXP = 20;

int iDeb[MAXN], iFin[MAXN], lazy[MAXN];
vector<int> adj[MAXN];
int sz[MAXN];
int depth[MAXN];
int par[MAXP][MAXN];
int heavyPar[MAXN];
int tin[MAXN];
int Time;

void push(int node) {
  if (iDeb[node] < iFin[node] and lazy[node] != -1) {
    lazy[2 * node] = lazy[2 * node + 1] = lazy[node];
    lazy[node] = -1;
  }
}

void build(int node, int l, int r, int defaultVal) {
  iDeb[node] = l, iFin[node] = r;
  lazy[node] = defaultVal;
  if (l == r)
    return;
  int m = (l + r) / 2;
  build(2 * node, l, m, defaultVal);
  build(2 * node + 1, m + 1, r, defaultVal);
}

void update(int node, int l, int r, int val) {
  push(node);
  if (l > iFin[node] or iDeb[node] > r)
    return;
  if (iDeb[node] >= l and iFin[node] <= r) {
    lazy[node] = val;
    push(node);
    return;
  }
  update(2 * node, l, r, val);
  update(2 * node + 1, l, r, val);
}

int query(int node, int pos) {
  push(node);
  if (pos > iFin[node] or pos < iDeb[node])
    return 0;
  if (iDeb[node] == iFin[node])
    return lazy[node];
  return query(2 * node, pos) + query(2 * node + 1, pos);
}

void dfsHLD(int u, int p) {
  sz[u] = 1;
  par[0][u] = p;
  for (int i = 0; i < MAXP - 1; ++i)
    par[i + 1][u] = par[i][par[i][u]];
  int largest = -1;
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfsHLD(v, u);
      sz[u] += sz[v];
      if (largest == -1 or sz[largest] < sz[v])
        largest = v;
    }

  if (largest != -1)
    for (int i = 1; i < (int)adj[u].size(); ++i)
      if (adj[u][i] == largest) {
        swap(adj[u][i], adj[u][0]);
        break;
      }
}

void dfs(int u, int p) {
  tin[u] = Time++;
  for (int i = 0; i < (int)adj[u].size(); ++i) {
    int v = adj[u][i];
    if (v == p)
      continue;
    if (!i)
      heavyPar[v] = heavyPar[u];
    else
      heavyPar[v] = v;
    dfs(v, u);
  }
}

int getLca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  int d = depth[u] - depth[v];
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & d)
      u = par[p][u];
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p) {
    int uu = par[p][u], vv = par[p][v];
    if (uu != vv)
      u = uu, v = vv;
  }
  return par[0][u];
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbSites, nbRequetes;
  cin >> nbSommets >> nbSites >> nbRequetes;

  for (int i = 0; i < nbSommets - 1; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfsHLD(0, 0);
  dfs(0, 0);

  vector<int> sites(nbSites);
  for (int &x : sites) {
    cin >> x;
    --x;
  }
  vector<pair<int, int>> inRMQ(nbSites);
  for (int i = 0; i < nbSites; ++i)
    inRMQ[i] = pair(tin[sites[i]], sites[i]);

  RMQ<pair<int, int>> maxSight(inRMQ);
  for (auto &[t, u] : inRMQ)
    t *= -1;
  RMQ<pair<int, int>> minSight(inRMQ);

  vector<int> solRequete(nbRequetes);
  vector<vector<pair<int, int>>> queriesAt(nbSites);
  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    queriesAt[l].emplace_back(r, iRequete);
  }
  for (int u = 0; u < nbSommets; ++u)
    dbg(u + 1, heavyPar[u] + 1);
  build(1, 0, nbSommets - 1, nbSites);

  Fenwick<int> withVal(nbSites + 1);
  withVal.upd(nbSites, nbSommets);
  for (int L = nbSites - 1; L >= 0; --L) {
    int u = sites[L];
    while (true) {
      int v = u;
      int val = query(1, tin[u]);
      for (int p = MAXP - 1; p >= 0; --p)
        if (val == query(1, tin[par[p][v]]))
          v = par[p][v];
      dbg(u + 1, v + 1, val);
      withVal.upd(val, -(depth[u] - depth[v] + 1));
      if (!v)
        break;
      u = par[0][v];
    }
    u = sites[L];
    while (true) {
      update(1, tin[heavyPar[u]], tin[u], L);
      dbg("UPDATE"s, 1 + heavyPar[u], 1 + u, L);
      withVal.upd(L, depth[u] - depth[heavyPar[u]] + 1);
      if (!heavyPar[u])
        break;
      u = par[0][heavyPar[u]];
    }

    for (auto [r, iRequete] : queriesAt[L]) {
      solRequete[iRequete] = withVal.sum(r + 1);
      int fst = minSight.query(L, r + 1).second;
      int lst = maxSight.query(L, r + 1).second;
      solRequete[iRequete] -= depth[getLca(fst, lst)];
    }
  }
  for (int x : solRequete)
    cout << x << '\n';
}

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