Submission #260345

#	Time	Username	Problem	Language	Result	Execution time	Memory
260345		arnold518	Valley (BOI19_valley)	C++14	100 / 100	359 ms	53496 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

struct Edge
{
	int u, v, w;
};

int N, S, Q, E;
Edge A[MAXN+10];
vector<pii> adj[MAXN+10];
bool P[MAXN+10];

int L[MAXN+10], R[MAXN+10], dep[MAXN+10], cnt, par[MAXN+10][30];
ll dist[MAXN+10], dp[MAXN+10][30];

void dfs(int now, int bef, int depp, ll distt)
{
	dep[now]=depp;
	dist[now]=distt;
	L[now]=++cnt;
	par[now][0]=bef;
	dp[now][0]=INF;
	if(P[now]) dp[now][0]=distt;
	for(auto &nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, depp+1, distt+nxt.second);
		dp[now][0]=min(dp[now][0], dp[nxt.first][0]);
	}
	R[now]=cnt;
}

int main()
{
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for(int i=1; i<N; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		A[i]={u, v, w};
	}
	for(int i=1; i<=S; i++)
	{
		int t;
		scanf("%d", &t);
		P[t]=1;
	}
	dfs(E, E, 1, 0);
	for(int i=1; i<=N; i++) dp[i][0]-=2*dist[i];
	for(int i=1; i<N; i++) if(dep[A[i].u]>dep[A[i].v]) swap(A[i].u, A[i].v);

	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
	{
		par[j][i]=par[par[j][i-1]][i-1];
		dp[j][i]=min(dp[j][i-1], dp[par[j][i-1]][i-1]);
	}

	while(Q--)
	{
		int t, u;
		scanf("%d%d", &t, &u);
		int v=A[t].v;
		if(!(L[v]<=L[u] && R[u]<=R[v])) printf("escaped\n");
		else
		{
			ll val=1e17;
			int now=u;
			for(int i=20; i>=0; i--)
			{
				if(dep[par[now][i]]>=dep[v])
				{
					val=min(val, dp[now][i]);
					now=par[now][i];
				}
			}
			val=min(val, dp[v][0]);
			if(val==(ll)1e17) printf("oo\n");
			else printf("%lld\n", val+dist[u]);
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:43: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:47: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:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
valley.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t, &u);
   ~~~~~^~~~~~~~~~~~~~~~

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