oj.uz

Submission #966510

# Submission time Handle Problem Language Result Execution time Memory
966510 2024-04-20T02:37:25 Z yellowtoad Valley (BOI19_valley) C++17
100 / 100
 403 ms 69388 KB 
#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;

long long n, m, q, root, cnt, id, d[100010];
pair<long long,long long> ed[100010], st[100010], ans[100010], tmp;
pair<long long,pair<long long,long long>> p[100010][20];
vector<pair<long long,long long>> edge[100010];

void dfs(int u, int v, long long depth) {
	st[u].f = ++cnt;
	d[u] = depth;
	for (int i = 0; i < edge[u].size(); i++) {
		if (edge[u][i].f != v) {
			dfs(edge[u][i].f,u,depth+edge[u][i].s);
			ans[u].f = min(ans[u].f,ans[edge[u][i].f].f+edge[u][i].s);
		}
	}
	st[u].s = ++cnt;
}

void dfs2(int u, int v) {
	p[u][0] = {v,min(ans[u],ans[v])};
	int tmp = v;
	for (int i = 1; i <= 19; i++) {
		p[u][i] = {p[tmp][i-1].f,min(p[u][i-1].s,p[tmp][i-1].s)};
		tmp = p[u][i].f;
	}
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs2(edge[u][i].f,u);
}

bool anc(int u, int v) {
	if ((st[u].f <= st[v].f) && (st[v].s <= st[u].s)) return 1;
	else return 0;
}

pair<long long,long long> lift(int u, int v) {
	long long i = 19;
	pair<long long, long long> minn = ans[u];
	while (i >= 0) {
		if ((p[u][i].f) && (!anc(p[u][i].f,v))) {
			minn = min(minn,p[u][i].s);
			u = p[u][i].f;
		}
		i--;
	}
	return minn;
}

int main() {
	long long u, v, w;
	cin >> n >> m >> q >> root;
	for (int i = 1; i < n; i++) {
		cin >> u >> v >> w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
		ed[i] = {u,v};
	}
	for (int i = 0; i <= n; i++) {
		ans[i] = {1e18,i};
		for (int j = 0; j <= 19; j++) p[i][j] = {0,{1e18,1e18}};
	}
	for (int i = 1; i <= m; i++) {
		cin >> u;
		ans[u].f = 0;
	}
	dfs(root,0,0);
	for (int i = 1; i <= n; i++) ans[i].f -= d[i];
	dfs2(root,0);
	while (q--) {
		cin >> id >> u;
		if (anc(ed[id].f,ed[id].s)) v = ed[id].s;
		else v = ed[id].f;
		if (anc(v,u)) {
			if (anc(ed[id].f,ed[id].s)) v = ed[id].f;
			else v = ed[id].s;
			tmp = lift(u,v);
			if (tmp.f+d[tmp.s] == 1e18) cout << "oo" << endl;
			else cout << tmp.f+d[tmp.s]+(d[u]-d[tmp.s]) << endl;
		} else cout << "escaped" << endl;
	}
}

Compilation message

valley.cpp: In function 'void dfs(int, int, long long int)':
valley.cpp:15:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i = 0; i < edge[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs2(edge[u][i].f,u);
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10840 KB Output is correct
2 Correct 16 ms 10844 KB Output is correct
3 Correct 20 ms 11132 KB Output is correct
4 Correct 16 ms 10844 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10840 KB Output is correct
2 Correct 16 ms 10844 KB Output is correct
3 Correct 20 ms 11132 KB Output is correct
4 Correct 16 ms 10844 KB Output is correct
5 Correct 4 ms 11096 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 10952 KB Output is correct
8 Correct 4 ms 10876 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 4 ms 10960 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10952 KB Output is correct
14 Correct 5 ms 10988 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 64828 KB Output is correct
2 Correct 342 ms 64596 KB Output is correct
3 Correct 361 ms 64844 KB Output is correct
4 Correct 383 ms 66688 KB Output is correct
5 Correct 350 ms 66872 KB Output is correct
6 Correct 403 ms 68800 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10840 KB Output is correct
2 Correct 16 ms 10844 KB Output is correct
3 Correct 20 ms 11132 KB Output is correct
4 Correct 16 ms 10844 KB Output is correct
5 Correct 4 ms 11096 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 10952 KB Output is correct
8 Correct 4 ms 10876 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 4 ms 10960 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10952 KB Output is correct
14 Correct 5 ms 10988 KB Output is correct
15 Correct 361 ms 64828 KB Output is correct
16 Correct 342 ms 64596 KB Output is correct
17 Correct 361 ms 64844 KB Output is correct
18 Correct 383 ms 66688 KB Output is correct
19 Correct 350 ms 66872 KB Output is correct
20 Correct 403 ms 68800 KB Output is correct
21 Correct 316 ms 64292 KB Output is correct
22 Correct 310 ms 64080 KB Output is correct
23 Correct 315 ms 64340 KB Output is correct
24 Correct 355 ms 66520 KB Output is correct
25 Correct 346 ms 69388 KB Output is correct
26 Correct 315 ms 64336 KB Output is correct
27 Correct 306 ms 64080 KB Output is correct
28 Correct 314 ms 64592 KB Output is correct
29 Correct 345 ms 65772 KB Output is correct
30 Correct 384 ms 67660 KB Output is correct
31 Correct 304 ms 64336 KB Output is correct
32 Correct 320 ms 64528 KB Output is correct
33 Correct 325 ms 64684 KB Output is correct
34 Correct 391 ms 66224 KB Output is correct
35 Correct 379 ms 69128 KB Output is correct
36 Correct 338 ms 66696 KB Output is correct