oj.uz

Submission #357734

# Submission time Handle Problem Language Result Execution time Memory
357734 2021-01-24T14:37:14 Z parsabahrami Valley (BOI19_valley) C++17
100 / 100
 420 ms 33824 KB 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
 
#define SZ(x)                       (ll) x.size()
#define F                           first
#define S                           second
#define lc 							id << 1
#define rc 							lc | 1

const ll N = 1e5 + 10, MOD = 1e9 + 7, INF = 1e18;
int V[N], S[N], L[N], R[N], n, q, k, M, timer; ll A[N], H[N], lazy[N << 2], seg[N << 2];
vector<pair<int, ll>> Q[N], adj[N]; pair<int, int> E[N];

void preDFS(int v, int p = -1) {
	L[v] = timer++;
	V[L[v]] = v;
	for (auto u : adj[v]) {
		if (u.F != p) {
			H[u.F] = H[v] + u.S;
			preDFS(u.F, v);
		}
	}
	R[v] = timer;
}

void build(int id = 1, int l = 0, int r = N) {
	if (r - l == 1) {
		if (S[V[l]]) seg[id] = H[V[l]];
		else seg[id] = INF;
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid, r);
	seg[id] = min(seg[lc], seg[rc]);
}

void shift(int id, int l, int r) {
	seg[id] += lazy[id];
	if (r - l > 1) {
		lazy[lc] += lazy[id];
		lazy[rc] += lazy[id];
	}
	lazy[id] = 0;
}

void update(int ql, int qr, ll x, int id = 1, int l = 0, int r = N) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) {
		lazy[id] += x;
		return shift(id, l, r);
	}
	int mid = (l + r) >> 1;
	update(ql, qr, x, lc, l, mid);
	update(ql, qr, x, rc, mid, r);
	seg[id] = min(seg[lc], seg[rc]);
}

ll get(int ql, int qr, int id = 1, int l = 0, int r = N) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return INF;
	if (ql <= l && r <= qr) return seg[id];
	int mid = (l + r) >> 1;
	return min(get(ql, qr, lc, l, mid), get(ql, qr, rc, mid, r));
}

int ispar(int v, int u) {
	return L[v] <= L[u] && R[u] <= R[v];
}

void DFS(int v, int p = -1) {
	for (auto u : Q[v]) {
		int eu = E[u.F].F, ev = E[u.F].S;
		if (H[eu] < H[ev]) swap(eu, ev);
		if (ispar(eu, v) == ispar(eu, M)) A[u.S] = -1;
		else {
			if (ispar(eu, v)) A[u.S] = get(L[eu], R[eu]);
			else A[u.S] = min(get(L[1], L[eu]), get(R[eu], R[1]));
		}
	}
	for (auto u : adj[v]) {
		if (u.F == p) continue;
		update(L[1], R[1], u.S);
		update(L[u.F], R[u.F], -2 * u.S);
		DFS(u.F, v);
		update(L[1], R[1], -u.S);
		update(L[u.F], R[u.F], 2 * u.S);
	}
}

int main() {
	scanf("%d%d%d%d", &n, &k, &q, &M);
	for (int i = 1; i < n; i++) {
		int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E[i].F = u, E[i].S = v;
	}
	for (int i = 1; i <= k; i++) {
		int v; scanf("%d", &v);
		S[v] = 1;
	}
	preDFS(1);
	build();
	for (int i = 1; i <= q; i++) {
		int v, l; scanf("%d%d", &l, &v);
		Q[v].push_back({l, i});
	}
	DFS(1);
	for (int i = 1; i <= q; i++) {
		if (A[i] == -1) printf("escaped\n");
		else if (A[i] <= (ll) 1e15) printf("%lld\n", A[i]);
		else printf("oo\n");
	}
    return 0;
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d%d%d%d", &n, &k, &q, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:98:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:104:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   int v; scanf("%d", &v);
      |          ~~~~~^~~~~~~~~~
valley.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   int v, l; scanf("%d%d", &l, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7660 KB Output is correct
2 Correct 10 ms 7660 KB Output is correct
3 Correct 10 ms 7660 KB Output is correct
4 Correct 11 ms 7660 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 25324 KB Output is correct
2 Correct 399 ms 25204 KB Output is correct
3 Correct 383 ms 25452 KB Output is correct
4 Correct 411 ms 28012 KB Output is correct
5 Correct 352 ms 27864 KB Output is correct
6 Correct 420 ms 33824 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7660 KB Output is correct
2 Correct 10 ms 7660 KB Output is correct
3 Correct 10 ms 7660 KB Output is correct
4 Correct 11 ms 7660 KB Output is correct
5 Correct 8 ms 7276 KB Output is correct
6 Correct 8 ms 7276 KB Output is correct
7 Correct 8 ms 7404 KB Output is correct
8 Correct 8 ms 7276 KB Output is correct
9 Correct 9 ms 7276 KB Output is correct
10 Correct 9 ms 7404 KB Output is correct
11 Correct 9 ms 7404 KB Output is correct
12 Correct 8 ms 7276 KB Output is correct
13 Correct 8 ms 7404 KB Output is correct
14 Correct 9 ms 7404 KB Output is correct
15 Correct 371 ms 25324 KB Output is correct
16 Correct 399 ms 25204 KB Output is correct
17 Correct 383 ms 25452 KB Output is correct
18 Correct 411 ms 28012 KB Output is correct
19 Correct 352 ms 27864 KB Output is correct
20 Correct 420 ms 33824 KB Output is correct
21 Correct 339 ms 24428 KB Output is correct
22 Correct 354 ms 24428 KB Output is correct
23 Correct 363 ms 24428 KB Output is correct
24 Correct 396 ms 26220 KB Output is correct
25 Correct 385 ms 31468 KB Output is correct
26 Correct 338 ms 24928 KB Output is correct
27 Correct 349 ms 24636 KB Output is correct
28 Correct 366 ms 24556 KB Output is correct
29 Correct 404 ms 27116 KB Output is correct
30 Correct 408 ms 30060 KB Output is correct
31 Correct 366 ms 25052 KB Output is correct
32 Correct 349 ms 24812 KB Output is correct
33 Correct 364 ms 24940 KB Output is correct
34 Correct 393 ms 26732 KB Output is correct
35 Correct 380 ms 30956 KB Output is correct
36 Correct 370 ms 27628 KB Output is correct