oj.uz

Submission #235643

# Submission time Handle Problem Language Result Execution time Memory
235643 2020-05-29T04:18:59 Z bharat2002 Valley (BOI19_valley) C++14
100 / 100
 358 ms 52000 KB 
/*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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2944 KB Output is correct
2 Correct 13 ms 3072 KB Output is correct
3 Correct 13 ms 2944 KB Output is correct
4 Correct 17 ms 2944 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2944 KB Output is correct
2 Correct 13 ms 3072 KB Output is correct
3 Correct 13 ms 2944 KB Output is correct
4 Correct 17 ms 2944 KB Output is correct
5 Correct 7 ms 3192 KB Output is correct
6 Correct 7 ms 3200 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 7 ms 3200 KB Output is correct
10 Correct 8 ms 3200 KB Output is correct
11 Correct 8 ms 3200 KB Output is correct
12 Correct 8 ms 3200 KB Output is correct
13 Correct 10 ms 3200 KB Output is correct
14 Correct 7 ms 3200 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 45560 KB Output is correct
2 Correct 292 ms 45304 KB Output is correct
3 Correct 305 ms 45560 KB Output is correct
4 Correct 358 ms 46712 KB Output is correct
5 Correct 223 ms 46972 KB Output is correct
6 Correct 345 ms 48120 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2944 KB Output is correct
2 Correct 13 ms 3072 KB Output is correct
3 Correct 13 ms 2944 KB Output is correct
4 Correct 17 ms 2944 KB Output is correct
5 Correct 7 ms 3192 KB Output is correct
6 Correct 7 ms 3200 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 7 ms 3200 KB Output is correct
10 Correct 8 ms 3200 KB Output is correct
11 Correct 8 ms 3200 KB Output is correct
12 Correct 8 ms 3200 KB Output is correct
13 Correct 10 ms 3200 KB Output is correct
14 Correct 7 ms 3200 KB Output is correct
15 Correct 301 ms 45560 KB Output is correct
16 Correct 292 ms 45304 KB Output is correct
17 Correct 305 ms 45560 KB Output is correct
18 Correct 358 ms 46712 KB Output is correct
19 Correct 223 ms 46972 KB Output is correct
20 Correct 345 ms 48120 KB Output is correct
21 Correct 177 ms 48932 KB Output is correct
22 Correct 203 ms 48504 KB Output is correct
23 Correct 207 ms 48760 KB Output is correct
24 Correct 218 ms 50168 KB Output is correct
25 Correct 271 ms 51960 KB Output is correct
26 Correct 179 ms 48760 KB Output is correct
27 Correct 183 ms 48504 KB Output is correct
28 Correct 200 ms 48760 KB Output is correct
29 Correct 247 ms 49656 KB Output is correct
30 Correct 310 ms 50808 KB Output is correct
31 Correct 189 ms 48888 KB Output is correct
32 Correct 212 ms 48632 KB Output is correct
33 Correct 250 ms 48888 KB Output is correct
34 Correct 284 ms 50040 KB Output is correct
35 Correct 259 ms 52000 KB Output is correct
36 Correct 263 ms 50040 KB Output is correct