Submission #310389

#	Time	Username	Problem	Language	Result	Execution time	Memory
310389		rqi	Valley (BOI19_valley)	C++14	100 / 100	509 ms	28408 KiB

valley

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

typedef long long ll;
typedef vector<int> vi;

#define f first
#define s second
#define pb push_back
#define mp make_pair

const int mx = 100005;
const ll INF = 1e18;
const ll BIG = 1e15;
int N, S, Q, E;
vector<pair<int, ll>> adj[mx];
int A[mx];
int B[mx];
ll W[mx];
bool isShop[mx];
int I[mx];
int R[mx];

bool esc[mx];
ll ans[mx];

vi queries[mx]; //queries at this node
bool inPath[mx];

void findPath(int node, int prv = -1){
	inPath[node] = 1;
	for(auto u: queries[node]){
		if(!inPath[A[I[u]]] || !inPath[B[I[u]]]){
			esc[u] = 1;
		}
	}

	for(auto u: adj[node]){
		if(u.f == prv) continue;
		findPath(u.f, node);
	}
	inPath[node] = 0;
}

ll dist[mx];
int depth[mx];
ll shop[mx]; //lowest shop dist

void genDists(int node, ll cdist = 0, int cdepth = 0, int prv = -1){
	dist[node] = cdist;
	depth[node] = cdepth;
	shop[node] = INF;

	if(isShop[node]){
		shop[node] = min(shop[node], dist[node]);
	}

	for(auto u: adj[node]){
		if(u.f == prv) continue;
		genDists(u.f, cdist+u.s, cdepth+1, node);
		shop[node] = min(shop[node], shop[u.f]);
	}
}

pair<int, ll> par[mx];
pair<int, ll> jmp[mx];

void genPar(int node, int prv = -1){
	if(node == E){
		par[node] = mp(node, INF);
		jmp[node] = mp(node, INF);
	}
	else{
		int p = par[node].f;
		if(depth[p]-depth[jmp[p].f] == depth[jmp[p].f]-depth[jmp[jmp[p].f].f]){
			jmp[node] = mp(jmp[jmp[p].f].f, min(par[node].s, min(jmp[p].s, jmp[jmp[p].f].s)));
		}
		else{
			jmp[node] = par[node];
		}
	}

	for(auto u: adj[node]){
		if(u.f == prv) continue;
		par[u.f] = mp(node, shop[node]);
		genPar(u.f, node);
	}
}

int main(){	
	cin >> N >> S >> Q >> E;
	for(int i = 1; i < N; i++){
		cin >> A[i] >> B[i] >> W[i];
		adj[A[i]].pb(mp(B[i], W[i]));
		adj[B[i]].pb(mp(A[i], W[i]));
	}

	for(int i = 1; i <= S; i++){
		int C;
		cin >> C;
		isShop[C] = 1;
	}

	for(int i = 1; i <= Q; i++){
		cin >> I[i] >> R[i];
		queries[R[i]].pb(i);
	}
	
	findPath(E); //modify esc
	genDists(E); //gen dist and depth
	for(int i = 1; i <= N; i++){
		shop[i]-=2*dist[i];
	}

	genPar(E);

	for(int i = 1; i <= Q; i++){
		if(esc[i]) continue;
		int topnode = max(mp(depth[A[I[i]]], A[I[i]]), mp(depth[B[I[i]]], B[I[i]])).s;
		int curnode = R[i];
		ll curans = shop[R[i]];
		while(curnode != topnode){
			if(depth[jmp[curnode].f] >= depth[topnode]){
				curans = min(curans, jmp[curnode].s);
				curnode = jmp[curnode].f;
			}
			else{
				curans = min(curans, par[curnode].s);
				curnode = par[curnode].f;
			}
		}
		ans[i] = curans+dist[R[i]];
	}
	for(int i = 1; i <= Q; i++){
		if(esc[i]){
			cout << "escaped" << "\n"; 
		}
		else{
			if(ans[i] >= BIG){
				cout << "oo" << "\n";
			}
			else{
				cout << ans[i] << "\n";
			}
		}
	}

}

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