Submission #217699

#	Time	Username	Problem	Language	Result	Execution time	Memory
217699		Fischer	Valley (BOI19_valley)	C++14	23 / 100	177 ms	19816 KiB

valley

#include <bits/stdc++.h>
#define re(x, y, z) for (int x=y; x<z; ++x)
#define trav(v, x) for (int v : x)
#define eb emplace_back
using namespace std;
const int maxn = 1e5 + 10;
long long h[maxn];
int lo[maxn], hi[maxn];
long long dist[maxn];
long long down[maxn];
using ii = pair<int, int>;
vector<ii> g[maxn];
int n, s, q, e;
ii edges[maxn];
int id[maxn];
bool shop[maxn];
priority_queue<ii, vector<ii>, greater<ii>> Q;
const long long inf = 1e18;
int T = 0;

long long dfs(int x, int p, long long he) {
	h[x] = he;
	lo[x] = T++;
	down[x] = shop[x] ? 0 : inf;
	for (auto node : g[x]) {
		if (node.first == p) continue;
		dfs(node.first, x, he + node.second);
		down[x] = min(down[x], down[node.first] + node.second);
	}
	hi[x] = T++;
}

bool isParent(int x, int y) {
	return lo[x] <= lo[y] and hi[y] <= hi[x];
}

void bfs() {
	while (!Q.empty()) {
		auto q = Q.top(); Q.pop();
		if (q.first != dist[q.second]) continue;
		for (auto node : g[q.second]) {
			if (q.first + node.second < dist[node.first]) {
				dist[node.first] = q.first + node.second;
				id[node.first] = id[q.second];
				Q.push({dist[node.first], node.first});
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d", &n, &s, &q, &e);
	re(i, 1, n) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		g[a].eb(b, w);
		g[b].eb(a, w);
		edges[i] = {a, b};
	}
	re(i, 1, n+1)
		dist[i] = inf; 
	re(i, 0, s) {
		int c;
		scanf("%d", &c);
		id[c] = c;
		dist[c] = 0;
		shop[c] = 1;
		Q.push({0, c});
	}
	dfs(e, 0, 0);
	bfs();
	re(i, 0, q) {
		int I, R;
		scanf("%d%d", &I, &R);
		int a = edges[I].first, b = edges[I].second;
		if (h[a] > h[b]) swap(a, b);
		if (isParent(b, R)) {
			if (down[b] == inf) puts("oo");		
			else {
				if (isParent(b, id[R])) {
					printf("%lld\n", dist[R]);
				} else {
					printf("%lld\n", down[b] + h[R] - h[b]);
				}
			}
		} else puts("escaped");
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'long long int dfs(int, int, long long int)':
valley.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
valley.cpp: In function 'int main()':
valley.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &s, &q, &e);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
valley.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &I, &R);
   ~~~~~^~~~~~~~~~~~~~~~

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