Submission #259016

#	Time	Username	Problem	Language	Result	Execution time	Memory
259016		Falcon	Valley (BOI19_valley)	C++14	100 / 100	396 ms	57388 KiB

valley

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif


using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

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

int N, S, Q, E;
vector<vector<edge>> adj;
vector<edge> edges;
vector<vi> par, RMQ_set;
vi is_shop, dp_set, in_time, out_time;
vector<ll> dp, dist;
vector<vector<ll>> RMQ;

void init(){
	adj.resize(N);
	dist.resize(N);
	dp.resize(N);
	is_shop.resize(N);
	dp_set.resize(N);
	in_time.resize(N);
	out_time.resize(N);
	edges.resize(N - 1);
	par = vector<vi>(N, vi(__lg(N) + 1, E));
	RMQ = vector<vector<ll>>(N, vector<ll>(__lg(N) + 1));
	RMQ_set = vector<vi>(N, vi(__lg(N) + 1));
}

int cur_time = 0;
void dfs(int v, int p, ll d){
	in_time[v] = cur_time++;
	debug(v);
	par[v][0] = p, dist[v] = d;
	if(is_shop[v])
		dp[v] = -d, dp_set[v] = 1;

	for(auto e : adj[v]){
		int u = v ^ e.v ^ e.u;
		if(u != p){
			dfs(u, v, d + e.w);
			if(dp_set[u]){
				if(!dp_set[v]) 
					dp[v] = dp[u] + 2 * e.w, dp_set[v] = 1;
				else 
					dp[v] =  min(dp[v], dp[u] + 2 * e.w);
			}
		}
	}
	out_time[v] = cur_time;
}

inline bool is_ancestor(int u, int v){
	return in_time[u] <= in_time[v] && out_time[v] <= out_time[u];
}

inline void xmin(ll a, int set_a, ll b, int set_b, ll& c, int& set_c){
	set_c = set_a || set_b;
	if(set_a && set_b)
		c = min(a, b);
	else if(set_a)
		c = a;
	else if(set_b)
		c = b;
}

void init_RMQ(){
	rep1(k, __lg(N))
		rep(i, N)
			par[i][k] = par[par[i][k - 1]][k - 1];
	rep(i, N)
		RMQ_set[i][0] = dp_set[i], RMQ[i][0] = dp[i];
	rep1(k, __lg(N))
		rep(i, N)
			xmin(RMQ[i][k - 1], RMQ_set[i][k - 1], RMQ[par[i][k - 1]][k - 1], RMQ_set[par[i][k - 1]][k - 1], RMQ[i][k], RMQ_set[i][k]);
}

pair<int, ll> nearest_shop(int r, int t){
	assert(is_ancestor(t, r));
	debug(r, t);
	ll d = dist[r];
	ll ans = -1;
	int set_ans = 0;
	int k = __lg(N);
	while(r != t){
		int x = par[r][k];
		debug(x, k);
		if(!is_ancestor(x, par[t][0]))
			xmin(RMQ[r][k], RMQ_set[r][k], ans, set_ans, ans, set_ans), r = x;
		k--;
	}
	xmin(ans, set_ans, RMQ[t][0], RMQ_set[t][0], ans, set_ans);
	return {set_ans, ans + d};
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    
    cin >> N >> S >> Q >> E;
    E--;

    init();

    rep(i, N - 1){
    	cin >> edges[i].u >> edges[i].v >> edges[i].w;
    	edges[i].u--, edges[i].v--;
    	adj[edges[i].u].pb(edges[i]), adj[edges[i].v].pb(edges[i]);
    }

    rep(i, S){
    	int v;
    	cin >> v;
    	is_shop[--v] = 1;
    }

    dfs(E, E, 0);
    init_RMQ();

    rep(i, Q){
    	int e, r;
    	cin >> e >> r;
    	--e, --r;
    	int t = dist[edges[e].u] < dist[edges[e].v] ? edges[e].v : edges[e].u;
    	if(!is_ancestor(t, r))
    		cout << "escaped\n";
    	else{
    		auto p = nearest_shop(r, t);
    		cout << (p.first ? to_string(p.second) : "oo") << '\n';
    	}
    }

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

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