Submission #258759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
258759	2020-08-06T14:07:37 Z	anubhavdhar	Valley (BOI19_valley)	C++14	100 / 100	617 ms	42604 KB

valley

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll ROOTN = 4;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

int N, Q, E, S, CLK, xt[MAXN], nt[MAXN], par[LOGN][MAXN], depcnt[MAXN];
ll dp[MAXN], sparse[LOGN][MAXN], dep[MAXN];
bool shop[MAXN];
vector<pair<int, ll>> g[MAXN];
vector<pair<pii, ll>> edge_list;

ll dfs(int a, int pp)
{
	nt[a] = CLK++;
	par[0][a] = pp;
	for(pair<int, ll> b : g[a])
		if(b.ff != pp)
		{
			dep[b.ff] = b.ss + dep[a];
			depcnt[b.ff] = 1 + depcnt[a];
			dp[a] = min(dp[a], dfs(b.ff, a) + b.ss);
		}
	if(shop[a])
		dp[a] = 0;
	for(pair<int, ll> b : g[a])
		if(b.ff != pp)
		{
			// cerr<<"sparse[0]["<<b.ff<<"] = "<<min(sparse[0][b.ff], b.ss + dp[a])<<'\n';
			sparse[0][b.ff] = min(sparse[0][b.ff], b.ss + dp[a]);
		}
	xt[a] = CLK++;
	return dp[a];
}

inline void init_sparse_table()
{
	F0Re(i, LOGN-1)
		F0Re(a, N)
			par[i][a] = (par[i-1][a] == -1) ? -1 : par[i-1][par[i-1][a]],
			sparse[i][a] = min(sparse[i-1][a],(((par[i-1][a]==-1) ? INF : (sparse[i-1][par[i-1][a]] + dep[a] - dep[par[i-1][a]]))));
}

inline void dbg_dp()
{
	F0Re(i, N)
		cerr<<"nt["<<i<<"] = "<<nt[i]<<" and xt["<<i<<"] = "<<xt[i]<<'\n';
}

inline void pre_process()
{
	CLK = 0;
	dep[E] = depcnt[E] = 0;
	F0Re(i, N)
		dp[i] = INF;
	F0R(i, LOGN)
		F0Re(a, N)
			sparse[i][a] = INF;
	dfs(E, -1);
	// dbg_dp();
	init_sparse_table();
}

inline void query(int e, int a)
{
	int u = (depcnt[edge_list[e].ff.ff] > depcnt[edge_list[e].ff.ss]) ? edge_list[e].ff.ff : edge_list[e].ff.ss;
	// cerr<<"u = "<<u<<" and a  = "<<a<<'\n';
	if(!(nt[u] <= nt[a] and xt[u] >= xt[a]))
	{
		cout<<"escaped\n";
		return;
	}
	int b = a;
	ll ans = dp[a];
	F0Rrev(i, LOGN-1)
	{
		if(par[i][b] == -1 or depcnt[par[i][b]] < depcnt[u])
			continue;
		ans = min(ans, sparse[i][b] + dep[a] - dep[b]);
		// cerr<<"considering "<<par[i][b]<<" and sparse["<<i<<"]["<<b<<"] = "<<sparse[i][b]<<'\n';
		b = par[i][b];
	}
	if(ans == INF)
		cout<<"oo\n";
	else
		cout<<ans<<'\n';
}

signed main()
{

	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/
	int j, k;
	ll len;
	cin>>N>>S>>Q>>E;
	F0R(i, N-1)
	{
		cin>>j>>k>>len;
		edge_list.pb(mp(mp(j, k), len));
		g[j].pb(mp(k,len));
		g[k].pb(mp(j,len));
	}

	F0Re(i, N)
		shop[i] = false;
	
	F0Re(i, S)
	{
		cin>>j;
		shop[j] = true;
	}


	// F0Re(i, N)
	// 	cerr<<shop[i]<<' ';
	// cerr<<'\n';

	pre_process();

	while(Q--)
	{
		cin>>j>>k;
		query(j-1, k);
	}	

	return 0;
}
/*
5 2 3 1 
1 2 3
1 3 2
3 4 1 
3 5 2 
2 4 
2 2 
2 5
4 5 

10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1
1 5
8 4
6 2
7 7

20 0 100 15
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1


*/

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	3064 KB	Output is correct
2	Correct	29 ms	3072 KB	Output is correct
3	Correct	29 ms	3200 KB	Output is correct
4	Correct	28 ms	3072 KB	Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	547 ms	36188 KB	Output is correct
2	Correct	571 ms	37868 KB	Output is correct
3	Correct	590 ms	37872 KB	Output is correct
4	Correct	588 ms	39908 KB	Output is correct
5	Correct	568 ms	40040 KB	Output is correct
6	Correct	617 ms	42084 KB	Output is correct

Subtask #4
41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	3064 KB	Output is correct
2	Correct	29 ms	3072 KB	Output is correct
3	Correct	29 ms	3200 KB	Output is correct
4	Correct	28 ms	3072 KB	Output is correct
5	Correct	6 ms	3200 KB	Output is correct
6	Correct	6 ms	3200 KB	Output is correct
7	Correct	6 ms	3200 KB	Output is correct
8	Correct	10 ms	3200 KB	Output is correct
9	Correct	6 ms	3200 KB	Output is correct
10	Correct	6 ms	3200 KB	Output is correct
11	Correct	6 ms	3200 KB	Output is correct
12	Correct	7 ms	3200 KB	Output is correct
13	Correct	6 ms	3200 KB	Output is correct
14	Correct	6 ms	3200 KB	Output is correct
15	Correct	547 ms	36188 KB	Output is correct
16	Correct	571 ms	37868 KB	Output is correct
17	Correct	590 ms	37872 KB	Output is correct
18	Correct	588 ms	39908 KB	Output is correct
19	Correct	568 ms	40040 KB	Output is correct
20	Correct	617 ms	42084 KB	Output is correct
21	Correct	517 ms	37876 KB	Output is correct
22	Correct	515 ms	37216 KB	Output is correct
23	Correct	543 ms	37476 KB	Output is correct
24	Correct	569 ms	39524 KB	Output is correct
25	Correct	559 ms	42604 KB	Output is correct
26	Correct	527 ms	37516 KB	Output is correct
27	Correct	520 ms	37248 KB	Output is correct
28	Correct	544 ms	37552 KB	Output is correct
29	Correct	555 ms	38884 KB	Output is correct
30	Correct	575 ms	40684 KB	Output is correct
31	Correct	510 ms	37476 KB	Output is correct
32	Correct	527 ms	37352 KB	Output is correct
33	Correct	537 ms	37676 KB	Output is correct
34	Correct	575 ms	39532 KB	Output is correct
35	Correct	577 ms	42596 KB	Output is correct
36	Correct	523 ms	39652 KB	Output is correct

Submission #258759

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 27.0 / 27.0

Subtask #3 23.0 / 23.0

Subtask #4 41.0 / 41.0

Subtask #1
9.0 / 9.0

Subtask #2
27.0 / 27.0

Subtask #3
23.0 / 23.0

Subtask #4
41.0 / 41.0