제출 #1127955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127955		sleepntsheep	Tourism (JOI23_tourism)	C++17	100 / 100	1322 ms	24532 KiB

tourism

/*model sol from joi website*/
#include <iostream>
#include <vector>
#include <queue>
#include <map>
struct binary_indexed_tree{
  int N;
  std::vector<int> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, int x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
int main(){
  int N, M, Q;
  std::cin >> N >> M >> Q;
  std::vector<std::vector<int>> E(N);
  for (int i = 0; i < N - 1; i++){
    int A, B;
    std::cin >> A >> B;
    A--;
    B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }
  std::vector<int> C(M);
  for (int i = 0; i < M; i++){
    std::cin >> C[i];
    C[i]--;
  }
  std::vector<int> L(Q), R(Q);
  for (int i = 0; i < Q; i++){
    std::cin >> L[i] >> R[i];
    L[i]--;
  }
  std::vector<int> p(N, -1);
  std::vector<std::vector<int>> c(N);
  std::queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (int w : E[v]){
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        q.push(w);
      }
    }
  }
  std::vector<int> sz(N);
  auto dfs1 = [&](auto dfs1, int v = 0) -> void {
    sz[v] = 1;
    for (int &w : c[v]){
      dfs1(dfs1, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        std::swap(w, c[v][0]);
      }
    }
  };
  dfs1(dfs1);
  std::vector<int> in(N);
  std::vector<int> next(N);
  next[0] = 0;
  int t = 0;
  auto dfs2 = [&](auto dfs2, int v = 0) -> void {
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(dfs2, w);
    }
  };
  dfs2(dfs2);
  std::vector<std::vector<int>> query(M);
  for (int i = 0; i < Q; i++){
    query[L[i]].push_back(i);
  }
  std::map<int, int> mp;
  mp[-1] = -1;
  mp[0] = M - 1;
  mp[N] = -1;
  std::vector<int> ans(Q, 0);
  binary_indexed_tree BIT(M - 1);
  for (int i = M - 2; i >= 0; i--){
    int u = C[i];
    int v = C[i + 1];
    if (u != v){
      std::vector<std::pair<int, int>> P;
      while (u != v){
        if (in[u] > in[v]){
          std::swap(u, v);
        }
        if (next[u] == next[v]){
          P.push_back(std::make_pair(in[u] + 1, in[v] + 1));
          break;
        }
        P.push_back(std::make_pair(in[next[v]], in[v] + 1));
        v = p[next[v]];
      }
      int cnt = P.size();
      for (int j = 0; j < cnt; j++){
        int l = P[j].first;
        int r = P[j].second;
        for (int k : {l, r}){
          if (mp.count(k) == 0){
            std::map<int, int>::iterator itr = std::prev(mp.lower_bound(k));
            int x = (*itr).second;
            mp[k] = x;
          }
        }
        while (true){
          std::map<int, int>::iterator itr = mp.lower_bound(l);
          int p1 = (*itr).first;
          if (p1 == r){
            break;
          }
          int p2 = (*std::next(itr)).first;
          int x = (*itr).second;
          if (x < M - 1){
            BIT.add(x, -(p2 - p1));
          }
          mp.erase(itr);
        }
        BIT.add(i, r - l);
        mp[l] = i;
        for (int k : {l, r}){
          std::map<int, int>::iterator itr = mp.lower_bound(k);
          if ((*itr).second == (*std::prev(itr)).second){
            mp.erase(itr);
          }
        }
      }
    }
    for (int j : query[i]){
      ans[j] = BIT.sum(i, R[j] - 1);
    }
  }
  for (int i = 0; i < Q; i++){
    ans[i]++;
  }
  for (int i = 0; i < Q; i++){
    std::cout << ans[i] << "\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