Submission #235643

#	Time	Username	Problem	Language	Result	Execution time	Memory
235643		bharat2002	Valley (BOI19_valley)	C++14	100 / 100	358 ms	52000 KiB

valley

/*input
5 1 1 1
1 2 3
1 3 2
3 4 1
3 5 2
2
2 5
4 5
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
const int N2=20;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int q, start[N], fin[N], dp[N], pv[N][N2], p[N][N2], depth[N], dist[N], n, e, s;vector< pii > adjlist[N];bool is[N];int ct;
void dfs(int i)
{
	dp[i]=inf;start[i]=ct++;
	for(auto j:adjlist[i])
	{
		if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=i;
		p[j.f][0]=i;dist[j.f]=dist[i]+1;
		dfs(j.f);
		dp[i]=min(dp[i], dp[j.f] + 2*depth[j.f] - 2*depth[i]);
	}
	if(is[i]) dp[i]=-depth[i];
	fin[i]=ct-1;
}
pii edges[N];
void solve()
{
	cin>>n>>s>>q>>e;ct=1;
	for(int i=1;i<=n;i++)
	{
		is[i]=0;start[i]=-1;
	}
	for(int i=1;i<n;i++)
	{
		int u, v, w;cin>>u>>v>>w;edges[i]=(mp(u, v));
		adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w));
	}
	while(s--)
	{
		int v;cin>>v;is[v]=1;
	}
	depth[e]=0;dist[e]=0;
	dfs(e);
	for(int i=1;i<=n;i++) pv[i][0]=dp[p[i][0]];
	for(int j=1;j<N2;j++)
		for(int i=1;i<=n;i++) {
			p[i][j]=p[p[i][j-1]][j-1];
			pv[i][j]=min(pv[i][j-1], pv[p[i][j-1]][j-1]);}
	while(q--)
	{
		int ind, r;cin>>ind>>r;
		int u=edges[ind].f, v=edges[ind].s;
		if(start[u]>start[v]) swap(u, v);
//		cout<<u<<" "<<v<<endl;
		if(start[v]<=start[r]&&fin[v]>=fin[r])
		{
			int diff=dist[r]-dist[v];int ans=dp[r];int add=depth[r];
//			cout<<diff<<endl;
			for(int i=N2-1;i>=0;i--)
			{
				if((1<<i)<=diff) {ans=min(ans, pv[r][i]);r=p[r][i];diff-=(1<<i);}
			}
			if(ans>=inf) cout<<"oo\n";
			else cout<<ans+add<<endl;
		}
		else cout<<"escaped\n";
	}
/*	for(int i=1;i<=n;i++)
	{
		cout<<i<<": "<<dp[i]<<endl;
	}*/
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t=1;
	while(t--)
	{
		solve();
	}
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int)':
valley.cpp:31:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=i;
   ^~
valley.cpp:31:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=i;
                               ^~~~~

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