Submission #357734

#	Time	Username	Problem	Language	Result	Execution time	Memory
357734		parsabahrami	Valley (BOI19_valley)	C++17	100 / 100	420 ms	33824 KiB

valley

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

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