Submission #1251714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251714		jtnydv25	Obstacles for a Llama (IOI25_obstacles)	C++20	83 / 100	205 ms	74396 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

struct dsu{
    int n;
    vector<int> par;
    dsu(){}
    dsu(int n) : n(n), par(n){
        iota(par.begin(), par.end(), 0);
    }
    int root(int x){
        return x == par[x] ? x : (par[x] = root(par[x]));
    }
    bool merge(int x, int y){
        x = root(x); y = root(y);
        if(x == y) return 0;
        par[x] = y;
        return 1;
    }
};
// 0-indexed
template<class T>
struct sparse_table{
    vector<vector<T>> arr; 
    vector<int> floorlog;
    function<T(T, T)> func;
    int n;
    sparse_table(){}
    sparse_table(vector<T> & vec, function<T(T, T)> f) : n(sz(vec)), floorlog(sz(vec) + 1), func(f){
        for(int i = 0; (1 << i) <= n; i++){
            for(int j = (1 << i); j < (1 << (i + 1)) && j <= n; j++)
                floorlog[j] = i;
        }
        arr.assign(floorlog[n] + 1, vector<T>(n));

        for(int i = n - 1; i >= 0; i--){
            arr[0][i] = vec[i];
            for(int j = 1; i + (1 << j) <= n; j++){
                arr[j][i] = func(arr[j - 1][i], arr[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int i, int j){
        int k = floorlog[j - i + 1];
        return func(arr[k][i], arr[k][j - (1 << k) + 1]);
    }

    pair<int, int> getRange(int i, function<bool(T)> pred) {
      int lo = i, hi = n - 1;
      while(lo < hi){
        int mid = (lo + hi + 1) / 2;
        if(pred(get(i, mid))) lo = mid;
        else hi = mid - 1;
      }
      int rgt = lo;
      lo = 0, hi = i;
      while(lo < hi){
        int mid = (lo + hi) / 2;
        if(pred(get(mid, i))) hi = mid;
        else lo = mid + 1;
      }
      int lft = lo;
      return {lft, rgt};
    }
};

struct Tree{
    vector<vector<int>> adj;
    vector<int> A, B, C;
    vector<ll> D; // weighted edges
    vector<int> pos, tour, depth, pos_end; // for O(1) lca after O(n logn) precomputation
    vector<vector<int>> table;

    int n, m;
    Tree(){}
    Tree(int n) : n(n), A(n - 1), B(n - 1), C(n - 1), adj(n), m(0){};

    void add_edge(int u, int v, int w = 1){
      if(u >= n || v >= n) {
        n = max(n, max(u, v) + 1);
        A.resize(n - 1); B.resize(n - 1); C.resize(n - 1);
        adj.resize(n);
      }
        adj[u].push_back(m);
        adj[v].push_back(m);
        A[m] = u; B[m] = v; C[m++] = w;
    }

    int argmin(int i, int j) { return depth[i] < depth[j] ? i : j; }
    void rootify(int r) {
        pos.resize(n);
        pos_end.resize(n);
        D.resize(n);
        function<void (int,int,int)> dfs = [&](int u, int p, int d) {
            pos[u] = pos_end[u] = depth.size();
            tour.push_back(u);
            depth.push_back(d);
            for (int ind: adj[u]) {
                int v = A[ind] ^ B[ind] ^ u;
                if (v != p) {
                    D[v] = D[u] + C[ind];
                    dfs(v, u, d+1);
                    pos_end[u] = depth.size();
                    tour.push_back(u);
                    depth.push_back(d);
                }
            }
        }; dfs(r, r, 0);
        int logn = __lg(tour.size());
        table.resize(logn+1, vector<int>(tour.size()));
        iota(all(table[0]), 0);
        for (int h = 0; h < logn; ++h) 
            for (int i = 0; i+(1<<h) < tour.size(); ++i)
                table[h+1][i] = argmin(table[h][i], table[h][i+(1<<h)]);
    }

    int lca(int u, int v) {
        int i = pos[u], j = pos[v]; if (i > j) swap(i, j);
        int h = __lg(j - i + 1);
        return i == j ? u : tour[argmin(table[h][i], table[h][j-(1<<h)+1])];
    }

    inline int getDepth(int u){
        return depth[pos[u]];
    }
    
    int dist(int u, int v){
        int l = lca(u, v);
        return D[u] + D[v] - 2 * D[l];
    }
};

dsu DSU;
struct TimedDSU{
  int n;
  vector<int> par, label;
  Tree T;
  TimedDSU() : n(0), T() {}
  TimedDSU(int n, int def_label): n(n), par(n), label(n, def_label), T(n){
    iota(par.begin(), par.end(), 0);
  }
  int root(int x){
    return x == par[x] ? x : (par[x] = root(par[x]));
  }
  void merge(int u, int v, int l){
    u = root(u); v = root(v);
    if(u == v) return;
    int w = n++;
    par[u] = par[v] = w;
    par.push_back(w);
    label.push_back(l);
    T.add_edge(u, w);
    T.add_edge(v, w);
  }
  void postprocess(){
    int w = n++;
    label.push_back(-1);
    for(int i = 0; i < w; i++) if(par[i] == i) T.add_edge(i, w);
    T.rootify(w);
  }

  int lcaLabel(int u, int v){
    return label[T.lca(u, v)];
  }
};
int n, m;
TimedDSU dsu_L, dsu_R;
void initialize(std::vector<int> T, std::vector<int> H) {
  n = T.size(), m = H.size();
  DSU = dsu(m);
  vector<int> prefMax(n);
  vector<int> lft(m), rgt(m), pos(m);
  vector<vector<int>> at_lft(m), at_rgt(m);
  sparse_table<int> st_H(H, [](int a, int b){return max(a, b);});
  sparse_table<int> st_T(T, [](int a, int b){return min(a, b);});
  for(int i = 0; i < n; i++){
    prefMax[i] = i == 0 ? 0: (T[i] > T[prefMax[i-1]] ? i : prefMax[i-1]);
  }
  for(int i = 0; i < m; i++){
    if(T[0] > H[i])
      pos[i] = prefMax[st_T.getRange(0, [&](int x){return x > H[i];}).second];
    else pos[i] = -1;
  }
  
  dsu_L = TimedDSU(m, m - 1); 
  dsu_R = TimedDSU(m, 0);
  stack<int> stk;
  for(int i = 0; i < m; i++){
    while(!stk.empty() && H[stk.top()] >= H[i])
      stk.pop();
    lft[i] = stk.empty() ? -1: stk.top();
    if(lft[i] != -1) {
      at_lft[lft[i]].push_back(i);
    }
    stk.push(i);
  }
  while(!stk.empty()) stk.pop();

  for(int i = m - 1; i >= 0; i--){
    while(!stk.empty() && H[stk.top()] > H[i]) stk.pop();
    rgt[i] = stk.empty() ? m: stk.top();
    if(rgt[i] != m) {
      at_rgt[rgt[i]].push_back(i);
    }
    stk.push(i);
  }
  // for(int L = m - 1; L >= 0; L--){
  //   for(int i: at_lft[L]){
  //     int j = pos[i];

  //     if(j == -1) continue;
  //     pair<int, int> rng = st_H.getRange(i, [&](int x){return x < T[j];});
  //     if(rgt[i] > rng.second){
  //       dsu_L.merge(i, L, L);
  //       DSU.merge(i, L);
  //     }
  //   }
  //   if(pos[L] != -1){
  //     pair<int, int> rng = st_H.getRange(L, [&](int x){return x < T[pos[L]];});
  //     if(rgt[L] <= rng.second){
  //       dsu_L.merge(L, rgt[L], L);
  //       DSU.merge(L, rgt[L]);
  //     }
  //   }
  // }
  // for(int R = 0; R < m; R++){
  //   for(int i: at_rgt[R]){
  //     int j = pos[i];
  //     if(j == -1) continue;
  //     pair<int, int> rng = st_H.getRange(i, [&](int x){return x < T[j];});
  //     if(lft[i] < rng.first){
  //       dsu_R.merge(i, R, R);
  //     }
  //   }
  //   if(pos[R] != -1){
  //     pair<int, int> rng = st_H.getRange(R, [&](int x){return x < T[pos[R]];});
  //     if(lft[R] >= rng.first){
  //       dsu_R.merge(R, lft[R], R);
  //     }
  //   }
  // }
  // dsu_L.postprocess();
  // dsu_R.postprocess();
  for(int i = 0; i < m; i++){
    int j = pos[i];
    if(j == -1) continue;
    pair<int, int> rng = st_H.getRange(i, [&](int x){return x < T[j];});
    if(rgt[i] <= rng.second) DSU.merge(i, rgt[i]);
    else if(lft[i] >= rng.first) DSU.merge(i, lft[i]);
  }
  return;
}

bool can_reach(int L, int R, int S, int D) {
  return DSU.root(S) == DSU.root(D);
  // int l = dsu_L.lcaLabel(S, D);
  // int r = dsu_R.lcaLabel(S, D);
  // if(l == -1 || r == -1) return false;
  // return L <= l && R >= r;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 25 / 25
• Subtask 6: 0 / 17