Submission #197044

#	Time	Username	Problem	Language	Result	Execution time	Memory
197044		arnold518	Valley (BOI19_valley)	C++14	100 / 100	338 ms	60280 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 = 1e15;

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

int N, S, Q, E;
vector<pii> adj[MAXN+10];
Edge edge[MAXN+10];
int C[MAXN+10];

int L[MAXN+10], R[MAXN+10], cnt, par[MAXN+10][35], dep[MAXN+10];
ll D[MAXN+10], EE[MAXN+10][35], F[MAXN+10];

bool reach(int I, int u, int v)
{
	bool a=(L[edge[I].v]<=L[u] && L[u]<=R[edge[I].v]);
	bool b=(L[edge[I].v]<=L[v] && L[v]<=R[edge[I].v]);
	return a==b;
}

void dfs(int now, int bef, ll dist, int depp)
{
	par[now][0]=bef;
	L[now]=R[now]=++cnt;

	D[now]=10*INF;
	if(C[now]) D[now]=dist;

	dep[now]=depp;

	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, dist+nxt.second, depp+1);
		R[now]=max(R[now], R[nxt.first]);
		D[now]=min(D[now], D[nxt.first]);
	}

	F[now]=dist;
	EE[now][0]=D[now]-2*dist;

	//printf("%d : %lld\n", now, EE[now][0]);
}

int main()
{
	int i, j;

	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for(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});
		edge[i]={u, v, w};
	}

	for(i=1; i<=S; i++)
	{
		int t;
		scanf("%d", &t);
		C[t]=1;
	}

	dfs(E, E, 0, 1);
	for(i=1; i<N; i++) if(L[edge[i].u]>L[edge[i].v]) swap(edge[i].u, edge[i].v);

	for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1], EE[j][i]=min(EE[j][i-1], EE[par[j][i-1]][i-1]);

	while(Q--)
	{
		int A, B;
		scanf("%d%d", &A, &B);

		if(reach(A, E, B)) { printf("escaped\n"); continue; }
		
		int now=B, to=edge[A].v;
		//printf("%d %d\n", now, to);
		ll ans=INF;
		if(C[now]) ans=0;
		for(i=20; i>=0; i--)
		{
			//printf("%d %d\n", par[now][i], i);
			if(dep[par[now][i]]>=dep[to])
			{
				ans=min(ans, EE[now][i]+F[B]);
				now=par[now][i];
			}
		}
		ans=min(ans, EE[to][0]+F[B]);

		if(ans==INF) printf("oo\n");
		else printf("%lld\n", ans);
	}
}

Compilation message (stderr)

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

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