Submission #217720

#	Time	Username	Problem	Language	Result	Execution time	Memory
217720		Fischer	Valley (BOI19_valley)	C++14	100 / 100	246 ms	41324 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];
const int LOG = 18;
int up[maxn][LOG];
long long st[maxn][LOG];
using lli = pair<long long, int>;
priority_queue<lli, vector<lli>, greater<lli>> Q;
const long long inf = 1e18;
int T = 0;
int step[maxn];

long long dfs(int x, int p, long long he) {
	h[x] = he;
	step[x] = step[p]+1;
	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++;
}

void dfs2(int x, int p) {
	st[x][0] = down[x] - h[x];
	up[x][0] = p==0?x:p;
	for (int k = 1; k < LOG; ++k) {
			st[x][k] = min(st[x][k-1], st[up[x][k-1]][k-1]);
			up[x][k] = up[up[x][k-1]][k-1];
	}
	for (auto node : g[x]) {
		if (node.first == p) continue;
		dfs2(node.first, x);
	}
}

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

void dikjstra() {
	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});
			}
		}
	}
}

long long query(int x, int y) {
	int len = step[x] - step[y] + 1;
	long long ans = inf;
	for (int k = 0; k < LOG; ++k) {
		if (len & (1<<k)) {
			ans = min(ans, st[x][k]);
			x = up[x][k];
		}
	}
	return ans;
}

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);
	dfs2(e, 0);
	dikjstra();
	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", query(R, b) + h[R]);
				}
			}
		} else puts("escaped");
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'long long int dfs(int, int, long long int)':
valley.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
valley.cpp: In function 'int main()':
valley.cpp:83: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:86: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:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
valley.cpp:106: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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41