Submission #1263650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263650		mingga	Valley (BOI19_valley)	C++20	100 / 100	207 ms	25244 KiB

valley

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const ll inf = 2e18;
const int N = 1e5 + 7;
int n, s, q, e;
pair<int, int> edge[N];
int in[N], out[N], timer;
bool mark[N];
ll ans[N], st[N * 4], lazy[N * 4], lev[N];
vector<pair<int, int>> g[N], ev[N];

void push(int i) {
	if(lazy[i]) {
		ll x = lazy[i];
		lazy[i] = 0;
		st[i * 2] += x;
		st[i * 2 + 1] += x;
		lazy[i * 2] += x;
		lazy[i * 2 + 1] += x;
	}
}

void update(int i, int l, int r, int u, int v, ll x) {
	if(l > v or r < u) return;
	if(u <= l and r <= v) {
		st[i] += x;
		lazy[i] += x;
		return;
	}
	push(i);
	int m = (l + r) >> 1;
	update(i * 2, l, m, u, v, x);
	update(i * 2 + 1, m + 1, r, u, v, x);
	st[i] = min(st[i * 2], st[i * 2 + 1]);
}

ll get(int i, int l, int r, int u, int v) {
	if(l > v or r < u) return inf;
	if(u <= l and r <= v) return st[i];
	push(i);
	int m = (l + r) >> 1;
	return min(get(i * 2, l, m, u, v), get(i * 2 + 1, m + 1, r, u, v));
}


void pre_dfs(int u, int p) {
	in[u] = ++timer;
	for(auto [v, w] : g[u]) {
		if(v == p) continue;
		lev[v] = lev[u] + w;
		pre_dfs(v, u);
	}
	out[u] = timer;
}

bool inside(int u, int v) {
	return in[u] <= in[v] and out[v] <= out[u];
}

void dfs(int u, int p) {
	for(auto [eid, id] : ev[u]) {
		auto [par, v] = edge[eid];
		if(inside(v, u)) {
			ans[id] = get(1, 1, n, in[v], out[v]);
		} else {
			ans[id] = min(get(1, 1, n, 1, in[v] - 1), get(1, 1, n, out[v] + 1, n));
		}
	}
	for(auto [v, w] : g[u]) {
		if(v == p) continue;
		update(1, 1, n, in[v], out[v], -w);
		update(1, 1, n, 1, in[v] - 1, w);
		update(1, 1, n, out[v] + 1, n, w);
		dfs(v, u);
		update(1, 1, n, in[v], out[v], w);
		update(1, 1, n, 1, in[v] - 1, -w);
		update(1, 1, n, out[v] + 1, n, -w);
	}
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		edge[i] = {u, v};
	}
	pre_dfs(1, 0);
	for(int i = 1; i < n; i++) {
		auto& [u, v] = edge[i];
		if(in[u] > in[v]) swap(u, v);
	}
	for(int i = 1; i <= s; i++) {
		int x; cin >> x;
		mark[x] = 1;
	}
	for(int i = 1; i <= q; i++) {
		int id, x; cin >> id >> x;
		auto [u, v] = edge[id];
		if(inside(v, e) and inside(v, x)) {
			ans[i] = -1;
		} else if(!inside(v, e) and !inside(v, x)) {
			ans[i] = -1;
		} else {
			ev[x].pb({id, i});
		}
	}
	for(int i = 1; i <= n; i++) {
		ll val = inf;
		if(mark[i]) val = lev[i];
		update(1, 1, n, in[i], in[i], val);
	}
	dfs(1, 0);
	for(int i = 1; i <= q; i++) {
		if(ans[i] == -1) cout << "escaped";
		else if(ans[i] > 1e15) cout << "oo";
		else cout << ans[i];
		cout << ln;
	}
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:96:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:97:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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