oj.uz

Submission #259016

# Submission time Handle Problem Language Result Execution time Memory
259016 2020-08-07T04:17:17 Z Falcon Valley (BOI19_valley) C++14
100 / 100
 396 ms 57388 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 784 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 52856 KB Output is correct
2 Correct 277 ms 52344 KB Output is correct
3 Correct 327 ms 52568 KB Output is correct
4 Correct 351 ms 54392 KB Output is correct
5 Correct 341 ms 54520 KB Output is correct
6 Correct 393 ms 56568 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 784 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 246 ms 52856 KB Output is correct
16 Correct 277 ms 52344 KB Output is correct
17 Correct 327 ms 52568 KB Output is correct
18 Correct 351 ms 54392 KB Output is correct
19 Correct 341 ms 54520 KB Output is correct
20 Correct 393 ms 56568 KB Output is correct
21 Correct 267 ms 52344 KB Output is correct
22 Correct 248 ms 51960 KB Output is correct
23 Correct 265 ms 51736 KB Output is correct
24 Correct 351 ms 54224 KB Output is correct
25 Correct 396 ms 57388 KB Output is correct
26 Correct 253 ms 52344 KB Output is correct
27 Correct 265 ms 51960 KB Output is correct
28 Correct 278 ms 51828 KB Output is correct
29 Correct 327 ms 53368 KB Output is correct
30 Correct 375 ms 55088 KB Output is correct
31 Correct 219 ms 52344 KB Output is correct
32 Correct 246 ms 51916 KB Output is correct
33 Correct 266 ms 51960 KB Output is correct
34 Correct 346 ms 54008 KB Output is correct
35 Correct 353 ms 57208 KB Output is correct
36 Correct 320 ms 54520 KB Output is correct