Submission #1108116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108116		orcslop	Valley (BOI19_valley)	C++17	0 / 100	128 ms	66784 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define f first
#define s second

template <typename T> class SparseTable {
  private:
    int n, log2dist; 
    vector<vector<T>> st;
  public:
    // build o(nlogn) query o(1)
    SparseTable(const vector<T> &v) {
        n = (int)v.size();
        log2dist = 1 + (int)log2(n);
        st.resize(log2dist);
        st[0] = v;
        for (int i = 1; i < log2dist; i++) {
            st[i].resize(n - (1 << i) + 1);
            for (int j = 0; j + (1 << i) <= n; j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    // minimum on 0-indexed range [l, r]
    T query(int l, int r) {
        int i = (int)log2(r - l + 1);
        return min(st[i][l], st[i][r - (1 << i) + 1]);
    }
};

class LCA {
  private:
    const int n;
    const vector<vector<int>> &adj;
    SparseTable<pair<int, int>> rmq;
    vector<int> tin, et, dep;
    int timer = 0;
    // prepares tin, et, dep vectors
    void dfs(int u, int p) {
        tin[u] = timer;
        et[timer++] = u;
        for (int v : adj[u]) {
            if (v == p) { continue; }
            dep[v] = dep[u] + 1;
            dfs(v, u);
            et[timer++] = u;
        }
    }
  public:
    // build o(nlogn) query o(1)
    // make sure the adjacency list is 0 indexed
    LCA(vector<vector<int>> &_adj)
        : n((int)_adj.size()), adj(_adj), tin(n), et(2 * n), dep(n),
          rmq(vector<pair<int, int>>(1)) {
        dfs(0, -1);
        vector<pair<int, int>> arr(2 * n);
        for (int i = 0; i < 2 * n; i++) { arr[i] = {dep[et[i]], et[i]}; }
        rmq = SparseTable<pair<int, int>>(arr);
    }
    // LCA of 0-indexed nodes a and b
    int query(int a, int b) {
        if (tin[a] > tin[b]) { swap(a, b); }
        return rmq.query(tin[a], tin[b]).second;
    }
};

struct Edge{
	int a, b, w; 
}; 

const int N = 1e5 + 5; 

int n, s, q, ex; 
bool shop[N]; 
int depth[N]; 
ll d[N]; 
ll mn[17][N]; 
int up[17][N]; 
vector<Edge> e; 
vector<vector<int>> cadj; 
vector<pair<int, int>> adj[N]; 

void dfs(int u, int v){
	up[0][u] = v; 
	mn[0][u] = (shop[u] ? 0 : 1e18); 
	for(auto x : adj[u]){
		if(x.f == v) continue; 
		d[x.f] = d[u] + x.s; 
		depth[x.f] = depth[u] + 1; 
		dfs(x.f, u); 
		mn[0][u] = min(mn[0][u], mn[0][x.f] + x.s); 
	}
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s >> q >> ex; ex--; 
    cadj.resize(n); 
    for(int i = 0; i < n - 1; i++){
    	int a, b, w; 
    	cin >> a >> b >> w; a--; b--; 
    	if(a == ex) a = 0; 
    	else if(a == 0) a = ex; 
    	if(b == ex) b = 0; 
    	else if(b == 0) b = ex; 
    	cadj[a].push_back(b); 
    	cadj[b].push_back(a); 
    	adj[a].push_back({b, w}); 
    	adj[b].push_back({a, w}); 
    	e.push_back({a, b, w}); 
    }
    for(int i = 0; i < s; i++){
    	int x; 
    	cin >> x; x--; 
    	if(x == ex) x = 0; 
    	else if(x == 0) x = ex; 
    	shop[x] = 1; 
    }
    dfs(0, 0); 
    LCA lca(cadj); 
    for(int i = 0; i < n; i++){
    	mn[0][i] -= d[i]; 
    }
    for(int i = 1; i < 17; i++){
    	for(int j = 0; j < n; j++){
    		up[i][j] = up[i - 1][up[i - 1][j]]; 
    		mn[i][j] = min(mn[i - 1][j], mn[i - 1][up[i - 1][j]]); 
    	}
    }
    for(int i = 0; i < n - 1; i++){
    	if(d[e[i].a] > d[e[i].b]){
    		swap(e[i].a, e[i].b); 
    	}
    }
    auto get_min = [&](int u, int g) -> ll{
    	ll ret = 1e18; 
    	for(int i = 0; i < 17; i++){
    		if(g & (1 << i)){
    			ret = min(ret, mn[i][u]); 
    			u = up[i][u]; 
    		}
    	}
    	return ret; 
    }; 
    while(q--){
    	int u, v; 
    	cin >> u >> v; u--; v--; 
    	int anc = e[u].b; 
    	if(lca.query(anc, v) == anc){
    		ll val = get_min(v, depth[v] - depth[anc] + 1); 
    		if(val > 1e15) cout << "oo\n"; 
    		else cout << val + d[v] << '\n'; 
    	}
    	else cout << "escaped\n"; 
    }
    return 0; 
}

Compilation message (stderr)

valley.cpp: In constructor 'LCA::LCA(std::vector<std::vector<int> >&)':
valley.cpp:37:26: warning: 'LCA::dep' will be initialized after [-Wreorder]
   37 |     vector<int> tin, et, dep;
      |                          ^~~
valley.cpp:36:33: warning:   'SparseTable<std::pair<int, int> > LCA::rmq' [-Wreorder]
   36 |     SparseTable<pair<int, int>> rmq;
      |                                 ^~~
valley.cpp:53:5: warning:   when initialized here [-Wreorder]
   53 |     LCA(vector<vector<int>> &_adj)
      |     ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41