oj.uz

Submission #217720

# Submission time Handle Problem Language Result Execution time Memory
217720 2020-03-30T13:56:30 Z Fischer Valley (BOI19_valley) C++14
100 / 100
 246 ms 41324 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 9 ms 2944 KB Output is correct
4 Correct 9 ms 2944 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 9 ms 2944 KB Output is correct
4 Correct 9 ms 2944 KB Output is correct
5 Correct 7 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3072 KB Output is correct
8 Correct 7 ms 3072 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 7 ms 3072 KB Output is correct
12 Correct 7 ms 3072 KB Output is correct
13 Correct 7 ms 3072 KB Output is correct
14 Correct 7 ms 3072 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 35040 KB Output is correct
2 Correct 205 ms 34532 KB Output is correct
3 Correct 220 ms 34408 KB Output is correct
4 Correct 235 ms 36396 KB Output is correct
5 Correct 225 ms 36324 KB Output is correct
6 Correct 246 ms 38244 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 8 ms 2816 KB Output is correct
3 Correct 9 ms 2944 KB Output is correct
4 Correct 9 ms 2944 KB Output is correct
5 Correct 7 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3072 KB Output is correct
8 Correct 7 ms 3072 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 7 ms 3072 KB Output is correct
12 Correct 7 ms 3072 KB Output is correct
13 Correct 7 ms 3072 KB Output is correct
14 Correct 7 ms 3072 KB Output is correct
15 Correct 205 ms 35040 KB Output is correct
16 Correct 205 ms 34532 KB Output is correct
17 Correct 220 ms 34408 KB Output is correct
18 Correct 235 ms 36396 KB Output is correct
19 Correct 225 ms 36324 KB Output is correct
20 Correct 246 ms 38244 KB Output is correct
21 Correct 185 ms 37008 KB Output is correct
22 Correct 189 ms 36340 KB Output is correct
23 Correct 193 ms 36088 KB Output is correct
24 Correct 205 ms 38112 KB Output is correct
25 Correct 220 ms 40824 KB Output is correct
26 Correct 181 ms 37100 KB Output is correct
27 Correct 196 ms 36468 KB Output is correct
28 Correct 200 ms 36216 KB Output is correct
29 Correct 216 ms 37496 KB Output is correct
30 Correct 228 ms 39032 KB Output is correct
31 Correct 185 ms 37352 KB Output is correct
32 Correct 200 ms 36720 KB Output is correct
33 Correct 210 ms 36724 KB Output is correct
34 Correct 227 ms 38512 KB Output is correct
35 Correct 237 ms 41324 KB Output is correct
36 Correct 224 ms 38896 KB Output is correct