oj.uz

Submission #629745

# Submission time Handle Problem Language Result Execution time Memory
629745 2022-08-15T03:19:57 Z dooompy Valley (BOI19_valley) C++17
100 / 100
 567 ms 56092 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2900 KB Output is correct
2 Correct 19 ms 2948 KB Output is correct
3 Correct 19 ms 2924 KB Output is correct
4 Correct 19 ms 2928 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2900 KB Output is correct
2 Correct 19 ms 2948 KB Output is correct
3 Correct 19 ms 2924 KB Output is correct
4 Correct 19 ms 2928 KB Output is correct
5 Correct 6 ms 3156 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 5 ms 3156 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 5 ms 3156 KB Output is correct
10 Correct 7 ms 3156 KB Output is correct
11 Correct 5 ms 3196 KB Output is correct
12 Correct 6 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 5 ms 3188 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 52544 KB Output is correct
2 Correct 450 ms 52308 KB Output is correct
3 Correct 511 ms 52616 KB Output is correct
4 Correct 549 ms 54124 KB Output is correct
5 Correct 509 ms 54408 KB Output is correct
6 Correct 557 ms 56092 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2900 KB Output is correct
2 Correct 19 ms 2948 KB Output is correct
3 Correct 19 ms 2924 KB Output is correct
4 Correct 19 ms 2928 KB Output is correct
5 Correct 6 ms 3156 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 5 ms 3156 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 5 ms 3156 KB Output is correct
10 Correct 7 ms 3156 KB Output is correct
11 Correct 5 ms 3196 KB Output is correct
12 Correct 6 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 5 ms 3188 KB Output is correct
15 Correct 427 ms 52544 KB Output is correct
16 Correct 450 ms 52308 KB Output is correct
17 Correct 511 ms 52616 KB Output is correct
18 Correct 549 ms 54124 KB Output is correct
19 Correct 509 ms 54408 KB Output is correct
20 Correct 557 ms 56092 KB Output is correct
21 Correct 429 ms 50880 KB Output is correct
22 Correct 444 ms 50836 KB Output is correct
23 Correct 480 ms 51036 KB Output is correct
24 Correct 556 ms 52600 KB Output is correct
25 Correct 567 ms 55164 KB Output is correct
26 Correct 410 ms 51136 KB Output is correct
27 Correct 425 ms 50812 KB Output is correct
28 Correct 532 ms 51072 KB Output is correct
29 Correct 547 ms 52252 KB Output is correct
30 Correct 525 ms 53636 KB Output is correct
31 Correct 441 ms 51180 KB Output is correct
32 Correct 456 ms 51104 KB Output is correct
33 Correct 493 ms 51632 KB Output is correct
34 Correct 563 ms 53036 KB Output is correct
35 Correct 563 ms 55248 KB Output is correct
36 Correct 551 ms 53124 KB Output is correct