Submission #125559

#	Time	Username	Problem	Language	Result	Execution time	Memory
125559		eriksuenderhauf	Valley (BOI19_valley)	C++11	100 / 100	289 ms	39772 KiB

valley

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define vii vector<pii>
#define vil vector<pil>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 7;
int par[19][MAXN], dep[MAXN];
int sh[MAXN], mrk[MAXN];
ll depth[MAXN], nx2[MAXN], nxPar[19][MAXN];
vil adj[MAXN];
pair<pii,ll> edg[MAXN];

void dfs(int u, int p, ll d, int d2) {
	depth[u] = d;
	dep[u] = d2;
	if (mrk[u]) 
		nx2[u] = d;
	else 
		nx2[u] = INF;
	for (pil nx: adj[u]) {
		int v; ll w;
		tie(v, w) = nx;
		if (v == p) continue;
		par[0][v] = u;
		dfs(v, u, d+w, d2+1);
		nx2[u] = min(nx2[u], nx2[v]);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	int d = dep[v]-dep[u];
	for (int i = 0; i < 19; i++)
		if ((d >> i) & 1)
			v = par[i][v];
	if (u == v) return u;
	for (int i = 18; i > -1; i--)
		if (par[i][u] != par[i][v])
			v = par[i][v], u = par[i][u];
	return par[0][u];
}

int main() {
	int n, s, q, e;
	scanf("%d %d %d %d", &n, &s, &q, &e);
	e--;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		u--, v--;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
		edg[i-1]=mp(mp(u,v),w);
	}
	for (int j = 0; j < s; j++) {
		scanf("%d", &sh[j]);
		mrk[--sh[j]] = 1;
	}
	dfs(e, -1, 0, 0);
	for (int i = 0; i < n; i++)
		if (nx2[i] != INF)
			nx2[i] -= 2*depth[i];
	for (int i = 0; i < n; i++)
		nxPar[0][i] = min(nx2[par[0][i]], nx2[i]);
	for (int i = 1; i < 19; i++) {
		for (int j = 0; j < n; j++) {
			par[i][j] = par[i-1][par[i-1][j]];
			nxPar[i][j] = min(nxPar[i-1][j],nxPar[i-1][par[i-1][j]]);
		}
	}
	while (q--) {
		int i, r;
		scanf("%d %d", &i, &r);
		i--, r--;
		int u, v;
		tie(u,v)=edg[i].fi;
		if (dep[u] < dep[v])
			swap(u,v);
		if (lca(r,u) != u) {
			printf("escaped\n");
			continue;
		}
		if (mrk[r]) {
			printf("0\n");
			continue;
		}
		int r0 = r;
		ll ans = nx2[r];
		int delta = dep[r] - dep[u];
		for (int i = 18; i > -1; i--)
			if ((delta >> i) & 1) {
				ans = min(ans, nxPar[i][r]);
				r = par[i][r];
			}
		if (ans == INF)
			printf("oo\n");
		else
			printf("%lld\n", ans+depth[r0]);
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:52: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:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sh[j]);
   ~~~~~^~~~~~~~~~~~~~
valley.cpp:80: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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41