Submission #966510

#	Time	Username	Problem	Language	Result	Execution time	Memory
966510		yellowtoad	Valley (BOI19_valley)	C++17	100 / 100	403 ms	69388 KiB

valley

#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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41