Submission #727531

#	Time	Username	Problem	Language	Result	Execution time	Memory
727531		cig32	Tourism (JOI23_tourism)	C++17	100 / 100	1518 ms	81128 KiB

tourism

#include "bits/stdc++.h"
#define int long long
using namespace std;
int n, m, q;
const int MAXN = 1e5+10;
vector<int> e;
vector<int> adj[MAXN];
int dep[MAXN];
int par[MAXN];
int tin[MAXN], cur;
vector<int> ord;
void dfs(int node, int prv) {
  e.push_back(node);
  ord.push_back(node);
  par[node] = prv;
  tin[node] = ++cur;
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  for(int x: adj[node]) {
    if(x != prv) {
      dfs(x, node);
      e.push_back(node);
    }
  }
}
int l[MAXN], r[MAXN];
pair<int,int> st[18][2 * MAXN];
int lca(int x, int y) {
  int m1 = min(l[x], l[y]), m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2-m1+1) - 1;
  return min(st[k][m1], st[k][m2-(1<<k)+1]).second;
}
int dist(int x, int y) {
  return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int c[MAXN], ans[MAXN];
bool radewoosh(pair<pair<int,int>,int>x,pair<pair<int,int>,int>y) {
  return x.first.second<y.first.second;
}
int dage[MAXN];
int pp[MAXN];
int bit[MAXN];
void add(int x, int v) {
  x++;
  for(;x<MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
  x++;
  int s=0;
  for(;x;x-=x&-x) s += bit[x];
  return s;
}
set<pair<pair<int,int>,int> >ss;
void update_range(int l, int r, int w) { // called n log n times, use at most log n
  auto it = ss.lower_bound({{l, 0}, 0});
  vector<pair<pair<int,int>,int> > rem, ins;
  ins.push_back({{l, r}, w});
  while(it != ss.end() && (*it).first.first <= r) {
    int ll = (*it).first.first, rr = (*it).first.second;
    int ww = (*it).second;
    if(rr <= r) {
      add(ww, -(rr-ll+1));
      rem.push_back(*it);
    }
    else {
      add(ww, -(rr-ll+1));
      rem.push_back(*it);
      ins.push_back({{r+1, rr}, ww});
    }
    it++;
  }
  it = ss.lower_bound({{l, 0}, 0});
  if(it != ss.begin()) {
    it--;
    int ll = (*it).first.first, rr = (*it).first.second, ww = (*it).second;
    if(rr < l) {
      // do nothing
    }
    else if(r < rr) {
      add(ww, -(rr-ll+1));
      rem.push_back(*it);
      ins.push_back({{ll, l-1}, ww});
      ins.push_back({{r+1, rr}, ww});
    }
    else {
      add(ww, -(rr-ll+1));
      rem.push_back(*it);
      ins.push_back({{ll, l-1}, ww});
    }
  }
  for(pair<pair<int,int>,int> pp : rem) {
    ss.erase(pp);
  }
  for(pair<pair<int,int>,int> pp : ins) {
    ss.insert(pp);
    add(pp.second, pp.first.second - pp.first.first + 1);
  }
}
int count_atleast(int x) { // number of >= x
  return sum(MAXN-2) - sum(x-1);
}
void update_path(int u, int v, int w) {
  int lc = lca(u, v);
  int fin = v;
  while(1) {
    int p1 = pp[u];
    int tar = dage[p1];
    if(dep[ord[tar]] < dep[lc]) tar = pp[lc];
    // [tar, p1]
    update_range(tar, p1, w-1);
    if(tar == pp[lc]) break;
    u = par[ord[tar]];
  }
  while(1) {
    int p1 = pp[v];
    int tar = dage[p1];
    if(dep[ord[tar]] < dep[lc]) tar = pp[lc];
    // [tar, p1]
    update_range(tar, p1, w-1);
    if(tar == pp[lc]) break;
    v = par[ord[tar]];
  }
  update_range(pp[fin], pp[fin], w);
}
int sz[MAXN];
void dfs0(int node, int prv) {
  sz[node] = 1;
  for(int x: adj[node]) {
    if(x != prv) {
      dfs0(x, node);
      sz[node] += sz[x];
    }
  }
}
bool hld(int x, int y) {
  return sz[x] > sz[y];
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> q;
  ss.insert({{1, n}, 0});
  add(0, n);
  for(int i=1; i<n; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  ord.push_back(0);
  dfs0(1, -1);
  for(int i=1; i<=n; i++) sort(adj[i].begin(), adj[i].end(), hld);
  dfs(1, -1);
  for(int i=1; i<=n; i++) {
    if(i == 1 || dep[ord[i]] <= dep[ord[i-1]]) dage[i] = i;
    else dage[i] = dage[i-1];
    pp[ord[i]] = i;
  }
  for(int i=0; i<e.size(); i++) r[e[i]] = i;
  for(int i=e.size()-1; i>=0; i--) l[e[i]] = i;
  for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<18; i++) {
    for(int j=0; j+(1<<i)-1<e.size(); j++) {
      st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  for(int i=1; i<=m; i++) cin >> c[i];
  pair<pair<int,int>,int> qry[q+1];
  for(int i=1; i<=q; i++) {
    cin >> qry[i].first.first >> qry[i].first.second;
    qry[i].second = i;
  }
  sort(qry+1, qry+1+q, radewoosh);
  int rr=0;
  c[0] = c[1];
  for(int i=1; i<=q; i++) {
    while(rr < qry[i].first.second) {
      rr++;
      update_path(c[rr-1], c[rr], rr);
    }
    ans[qry[i].second] = count_atleast(qry[i].first.first);
  }
  for(int i=1; i<=q; i++) {
    cout << ans[i] << "\n";
  }
}
// 2 1 0 0 3 2 0 0
/*
5 5 15
1 2 2 3 3 4 4 5
2 4 5 1 3
1 1 1 2 1 3 1 4 1 5 2 2 2 3 2 4 2 5 3 3 3 4 3 5 4 4 4 5 5 5

g++ C.cpp -std=c++17 -o C
g++ Csmall.cpp -std=c++17 -o Csmall
g++ gen.cpp -std=c++17 -o gen
g++ checker.cpp -std=c++17 -o checker

for((i=1; ; ++i)); do
  ./gen $i > input_file
  ./C < input_file > myAnswer
  ./Csmall < input_file > correctAnswer
  ./checker > checker_log
  echo "Passed test: " $i
done
*/

Compilation message (stderr)

tourism.cpp: In function 'int32_t main()':
tourism.cpp:158:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   for(int i=0; i<e.size(); i++) r[e[i]] = i;
      |                ~^~~~~~~~~
tourism.cpp:160:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
      |                ~^~~~~~~~~
tourism.cpp:162:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for(int j=0; j+(1<<i)-1<e.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~

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