Submission #629745

#	Time	Username	Problem	Language	Result	Execution time	Memory
629745		dooompy	Valley (BOI19_valley)	C++17	100 / 100	567 ms	56092 KiB

valley

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define int ll
 
vector<pair<int, ll>> adj[100005];
 
int height[100005], jmp[100005][20];
 
int tin[100005], timer = 1;
 
int rev[100005];
 
ll best[100005];
 
struct querystr {
	int a, b, c;
};
 
//~ void prop(int node) {
	//~ for (auto a : adj[node]) {
		//~ if (height[a.first] < height[node]) continue;
		
		//~ if (best[a.first] > best[node] + a.second) {
			//~ best[a.first] = best[node] + a.second;
			//~ prop(a.first);
		//~ }
		
	//~ }
//~ }
 
void dfs(int node) {
	tin[node] = timer++;
	rev[tin[node]] = node;
	for (int i = 1; i < 20; i++) {
		jmp[node][i] = jmp[jmp[node][i-1]][i-1];
	}
	
	for (auto nxt : adj[node]) {
		if (height[nxt.first]) continue;
		
		height[nxt.first] = height[node] + 1;
		jmp[nxt.first][0] = node;
		
		dfs(nxt.first);
	}
}
 
int lca(int a, int b) {
	if (height[a] > height[b]) swap(a, b);
	
	for (int i = 19; i >= 0; i--) {
		if (height[jmp[b][i]] >= height[a]) b = jmp[b][i];
	}
	
	if (a == b) return a;
	
	for (int i = 19; i >= 0; i--) {
		if (jmp[a][i] != jmp[b][i]) {
			a = jmp[a][i]; b = jmp[b][i];
		}
	}
	
	return jmp[a][0];
}
 
ll val[100005];
ll sump[100005];
bool shop[100005];
ll mintoshop[100005];
 
void precalc(int node) {
 
	for (auto nxt : adj[node]) {
		if (height[nxt.first] < height[node]) continue;
		sump[nxt.first] = sump[node] + nxt.second;
		precalc(nxt.first);
	}
	if (shop[node]) {
		mintoshop[node] = sump[node];
	} else {
		mintoshop[node] = LLONG_MAX/2;
		
		for (auto nxt : adj[node]) {
			if (height[nxt.first] < height[node]) continue;
			mintoshop[node] = min(mintoshop[node], mintoshop[nxt.first]);
		}
	}
}
 
void build(int node) {
	
	for (auto nxt : adj[node]) {
		if (height[nxt.first] < height[node]) continue;
		build(nxt.first);
	}
	
	if (shop[node]) {
		val[node] = -1 * sump[node];
	} else {
		val[node] = LLONG_MAX/2;
				
		
		if (mintoshop[node] < LLONG_MAX/3) {
			val[node] = -2 * sump[node] + mintoshop[node];
		}
	}
	
	//~ cout << node << " " << val[node] << endl;
}
 
ll minjmp[100005][20];
 
void lcaagain(int node) {
	minjmp[node][0] = min(val[node], val[jmp[node][0]]);
	
	for (int i = 1; i < 20; i++) {
		minjmp[node][i] = min(minjmp[node][i-1], minjmp[jmp[node][i-1]][i-1]);
		//~ cout << node << " " << i << " " << minjmp[node][i] << endl;
	}
	
	for (auto nxt : adj[node]) {
		if (height[nxt.first] < height[node]) continue;
		lcaagain(nxt.first);
	}
}
 
struct edge {
	int a, b; ll c;
};
 
vector<edge> edges;
 
int32_t main() {
	int n, s, e, q; cin >> n >> s >> q >> e;
 
	for (int i = 0; i < n-1; i++) {
		int a, b; ll c; cin >> a >> b >> c;
		edges.push_back({a, b, c});
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	
	vector<int> shops;
	
	for (int i = 0; i < s; i++) {
		int a; cin >> a;
		shop[a] = true;
		shops.push_back(a);
	}
	
	height[e] = 1;
	jmp[e][0] = e;
	dfs(e);
	
	vector<querystr> todo;
	vector<int> answer(q);
	
	precalc(e);
	build(e);
	lcaagain(e);
	
	for (int i = 0; i < q; i++) {
		int rd, loc; cin >> rd >> loc;
		rd--;
		int greaterd = (height[edges[rd].a] > height[edges[rd].b] ? edges[rd].a : edges[rd].b);
		
		if (lca(loc, greaterd) == greaterd) {
			if (shop[loc]) {
				cout << "0\n";
				continue;
			}
			
			
			ll minval = val[loc];
			
			int temploc = loc;
			for (int i = 19; i >= 0; i--) {
				// loc -> greaterd
				
				if (height[jmp[temploc][i]] >= height[greaterd]) {
					minval = min(minval, minjmp[temploc][i]);
					temploc = jmp[temploc][i];
				}
			}
			
			if (minval >= LLONG_MAX/3) cout << "oo\n";
			else cout << minval + sump[loc] << "\n";
			
			//~ todo.push_back({greaterd, i, loc});
			
			//~ priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
			//~ pq.push({0, loc});
			
			//~ vector<ll> dist(100005, LLONG_MAX/2);
			//~ dist[loc] = 0;
			
			//~ bool done = false;
			
			//~ while (!pq.empty()) {
				//~ auto cur = pq.top(); pq.pop();
				
				//~ if (cur.first != dist[cur.second]) continue;
				
				//~ if (shop[cur.second]) {
					//~ cout << cur.first << "\n";
					//~ done = true;
					//~ break;
				//~ }
				
				//~ for (auto nxt : adj[cur.second]) {
					//~ if (cur.second == greaterd && nxt.first == jmp[cur.second][0]) continue;
					//~ if (dist[nxt.first] <= cur.first + nxt.second) continue;
					
					//~ dist[nxt.first] = cur.first + nxt.second;
					
					//~ pq.push({cur.first + nxt.second, nxt.first});
				//~ }
			//~ }
			
			//~ if (!done) {
				//~ cout << "oo\n";
				//~ continue;
			//~ }
						
		} else cout << "escaped\n";
	}
	
	//~ sort(todo.begin(), todo.end(), [](querystr a, querystr b) {
		//~ return tin[a.a] > tin[b.a];
	//~ });
	
	
	//~ for (auto a : todo) {
		//~ cout << a.first << " " << a.second << endl;
	//~ }
	
	//~ int idx = 0;
	
	//~ fill(best, best+100005, LLONG_MAX/2);
	
	//~ for (int i = timer-1; i >= 1; i--) {
		//~ // rev[i]
		//~ int cur = rev[i];
		
		//~ if (shop[cur]) {
			//~ best[cur] = 0;
			
			//~ // check downards
			
			//~ prop(cur);
			
			
		//~ } else {
			//~ best[cur] = LLONG_MAX / 2;
			//~ for (auto a : adj[cur]) {
				//~ if (height[a.first] < height[cur]) continue;
				//~ best[cur] = min(best[cur], a.second + best[a.first]);
			//~ }
		//~ }
		
		//~ cout << cur << " " << best[cur] << endl;
		
		//~ if (idx < todo.size() && todo[idx].a == cur) {
			//~ answer[todo[idx].b] = best[todo[idx].c];
			//~ idx++;
		//~ }
	//~ }
	
	//~ for (auto ans : answer) {
		//~ if (ans == -1) cout << "escaped\n";
		//~ else if (ans == LLONG_MAX/2) cout << "oo\n";
		//~ else cout << ans << "\n";
	//~ }
}

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