Submission #901891

#	Time	Username	Problem	Language	Result	Execution time	Memory
901891		aqxa	Valley (BOI19_valley)	C++17	100 / 100	512 ms	47668 KiB

valley

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

#define ll long long

const int N = 1e5 + 10; 
const ll inf = 1e18; 

int n, m, q, rt, s[N], gs[N] = { 0 }; 
vector<pair<int, int>> g[N];
pair<int, int> edges[N]; 
set<int> nd[N]; 
map<int, ll> ans[N]; 

int lv = 0, lev[N]; 
vector<vector<int>> par(N, vector<int>(17, -1)); 
vector<int> path; 
void make_lca(int x, int p) {
	path.push_back(x);
	lv++;
	lev[x] = lv;
	
	for (int i = 0; (1 << i) < path.size(); ++i) {
		par[x][i] = path[path.size()-1-(1<<i)];
	}
	
	for (auto [u, w]: g[x]) {
		if (u != p) {
			make_lca(u, x);
		}
	}
	lv--;
	path.pop_back();
}
int ka(int u, int k) {
	if (k > lev[u] - 1) return 0; 
	while (k > 0) {
		int lg = (int) __lg(k);  
		k -= pow(2, lg);
		u = par[u][lg];
	}
	
	return u;
}

int lca(int u, int v) {
	int du = lev[u], dv = lev[v];
	if (du < dv) {
		v = ka(v, dv-du);
		dv = du;
	} else if (du > dv) {
		u = ka(u, du-dv);
		du = dv;
	}

	if (u == v) return u;

	for (int i = 17-1; i >= 0; --i) {
		if (par[u][i] != par[v][i]) {
			u = par[u][i];  
			v = par[v][i];
		}
	}

	return par[u][0];
}

ll dst[N]; 
void dfs_st(int x, int p) {
	dst[x] = inf; 
	if (gs[x]) dst[x] = 0; 
	for (auto [u, w]: g[x]) {
		if (u == p) continue; 
		dfs_st(u, x); 
		dst[x] = min(dst[x], dst[u] + (ll) w); 
	}
}

ll tree[262144] = { inf }, lazy[262144] = { 0 }; 
void push(int L, int R, int id) {
	tree[id] += lazy[id]; 
	if (L != R) for (int i = 0; i < 2; ++i) lazy[2 * id + i] += lazy[id]; 
	lazy[id] = 0; 
}
void pull(int id) { tree[id] = min(tree[2 * id], tree[2 * id + 1]); }
void ch(int x, ll y, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (x < L || R < x) return;
	if (L == x && x == R) { tree[id] = y; return;  }
	int M = (L+R)/2; ch(x, y, L, M, 2 * id); 
	ch(x, y, M + 1, R, 2 * id + 1); pull(id);
}
void add(int l, int r, ll v, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (r < L || R < l) return;
	if (l <= L && R <= r) { lazy[id] = v; push(L, R, id); return; }
	int M = (L+R)/2; add(l, r, v, L, M, 2 * id); 
	add(l, r, v, M + 1, R, 2 * id + 1); pull(id);
}
ll get(int l, int r, int L = 0, int R = 131072 - 1, int id = 1) {
	push(L, R, id); if (r < L || R < l) return inf; 
	if (l <= L && R <= r) return tree[id]; 
	int M = (L+R)/2;
	return min(get(l, r, L, M, 2 * id), get(l, r, M + 1, R, 2 * id + 1));
}


int csz = 0; 
void dfs_ans(int x, int p) {
	ch(csz, dst[x]); 

	for (auto u: nd[x]) {
		int ld = lev[x] - lev[u]; 
		ans[x][u] = get(csz - ld, csz); 
	}
	csz++; 

	for (auto [u, w]: g[x]) {
		if (u == p) continue; 
		add(0, csz, (ll)w); 
		dfs_ans(u, x); 
		add(0, csz, (ll)-w); 
	}

	csz--; 
	ch(csz, inf); 
}

int main() {
	cin >> n >> m >> q >> rt; 
	for (int i = 0; i < n - 1; ++i) {
		int x, y, w; 
		cin >> x >> y >> w; 
		edges[i] = make_pair(--x, --y); 
		g[x].push_back({y, w}); 
		g[y].push_back({x, w}); 
	}
	for (int i = 0; i < m; ++i) {
		cin >> s[i]; 
		gs[--s[i]] = 1; 
	}
	make_lca(--rt, -1); 

	int qi[q], qs[q]; 
	for (int i = 0; i < q; ++i) {
		cin >> qi[i] >> qs[i]; 
		qi[i]--; qs[i]--; 
		
		int x = edges[qi[i]].first, y = edges[qi[i]].second; 
		int z = lca(x, y) ^ x ^ y; 
		if (lca(z, qs[i]) == z) {
			nd[qs[i]].insert(z); 
		} 
	}
	
	dfs_st(rt, -1); 
	dfs_ans(rt, -1); 
	for (int i = 0; i < q; ++i) {
		int x = edges[qi[i]].first, y = edges[qi[i]].second; 
		int z = lca(x, y) ^ x ^ y; 
		if (lca(z, qs[i]) == z) {
			ll cans = ans[qs[i]][z]; 
			if (cans == inf) cout << "oo\n";
			else cout << cans << "\n";
		} else {
			cout << "escaped\n";
		}
	}

	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void make_lca(int, int)':
valley.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; (1 << i) < path.size(); ++i) {
      |                  ~~~~~~~~~^~~~~~~~~~~~~

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