Submission #1096545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096545		flo	Valley (BOI19_valley)	C++14	100 / 100	118 ms	50264 KiB

valley

#include <bits/stdc++.h>
#define fi first
#define se second
#define str string
#define pb push_back
#define mp make_pair
#define ll long long
#define lld long double
#define pr pair<int, ll>
#define mat vector<vector<ll>>
#define ull unsigned long long
#define srt(a) sort(a.begin(), a.end())
#define Kimishima cin.tie(0); cout.tie(0);
#define Ayano ios_base::sync_with_stdio(false);
#define dec(u, v) setprecision(v) << fixed << u
#define uni(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define left(a, v) (lower_bound(a.begin(), a.end(), v)-a.begin())
using namespace std;
const ll lim = 1e5, inf = 1e18;
struct Edge {int u, v; ll w;} e[lim+5];
ll dis[lim+5], dp[lim+5]; pr lf[18][lim+5]; 
int cnt, h[lim+5], pos[2][lim+5]; vector<pr> adj[lim+5];
void dfs(int v, int par) {
	pos[0][v] = cnt++;
	for (auto u : adj[v]) {
		if (u.fi == par) continue;
		h[u.fi] = h[v]+1, lf[0][u.fi].fi = v; 
		dis[u.fi] = dis[v]+u.se; dfs(u.fi, v);
		dp[v] = min(dp[v], dp[u.fi]+u.se);
	}
	pos[1][v] = cnt-1;
}
ll get(int cur, int k) {
	ll ans = inf;
	for (int x = 17; x >= 0; x--) {
		if (k&(1<<x)) {
			ans = min(ans, lf[x][cur].se); 
			cur = lf[x][cur].fi;
		}
	}
	return ans;
}
void query(int d, int r) {
	int u = e[d].u, v = e[d].v;
	if (pos[0][u] > pos[0][v]) swap(u, v);
	if (pos[0][v] > pos[0][r]) {
		cout << "escaped\n"; return;
	}
	if (pos[1][r] > pos[1][v]) {
		cout << "escaped\n"; return;
	}
	ll ans = get(r, h[r]-h[u]);
	if (ans+dis[r] >= inf) cout << "oo\n";
	else cout << ans+dis[r] << "\n"; return;
}
void solve() {
	int n, s, q, h; cin >> n >> s >> q >> h;
	for (int x = 1; x < n; x++) {
		cin >> e[x].u >> e[x].v >> e[x].w;
		adj[e[x].u].pb(mp(e[x].v, e[x].w));
		adj[e[x].v].pb(mp(e[x].u, e[x].w));
	}
	for (int x = 1; x <= n; x++) dp[x] = inf;
	for (int x = 1; x <= s; x++) {
		int cur; cin >> cur; dp[cur] = 0;
	}
	for (int x = 1; x <= 17; x++) {
		for (int y = 1; y <= n; y++) lf[x][y].se = inf;
	}
	cnt = 1; dfs(h, 0); 
	for (int x = 1; x <= n; x++) {
	    lf[0][x].se = dp[x]-dis[x];
	}
	for (int x = 1; x <= 17; x++) {
		for (int y = 1; y <= n; y++) {
			lf[x][y] = lf[x-1][lf[x-1][y].fi];
			lf[x][y].se = min(lf[x][y].se, lf[x-1][y].se);
		}
	}
	while (q--) {
		int d, r; cin >> d >> r; query(d, r);
	}
	cout << "\n"; return;
}
int main() {
    Ayano Kimishima
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1; while (t--) solve(); return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void query(int, int)':
valley.cpp:54:2: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   54 |  else cout << ans+dis[r] << "\n"; return;
      |  ^~~~
valley.cpp:54:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   54 |  else cout << ans+dis[r] << "\n"; return;
      |                                   ^~~~~~

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