oj.uz

Submission #497906

# Submission time Handle Problem Language Result Execution time Memory
497906 2021-12-24T04:36:45 Z armashka Valley (BOI19_valley) C++17
100 / 100
 372 ms 91232 KB 
#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
ll n, s, k, e, dp[N], in[N], out[N], timer, up[N][30], mnn[N][30], sel[N], h[N], d[N];
pll edge[N];
vector <pll> g[N];
 
void dfs(ll v, ll pr) {
	up[v][0] = pr;
	in[v] = ++ timer;
	ll mn = inf;
	for (auto [to, w] : g[v]) {
		if (to != pr) {
			h[to] = h[v] + 1;
			d[to] = d[v] + w;
			dfs(to, v);
			mn = min(mn, dp[to] + w);			
		}
	}
	if (sel[v]) mn = 0;
	dp[v] = mn;
	for (auto [to, w] : g[v]) {
		if (to != pr) {
			mnn[to][0] = dp[v] - d[v];
		}
	}
	out[v] = ++ timer;
}
 
ll get(ll u, ll v, ll pr) {
	if (in[v] >= in[pr] && out[v] <= out[pr]);
	else return inf;
	ll mn = dp[v] + (d[u] - d[v]);
	for (int i = 0; i <= 25; ++ i) {
		ll cur = up[v][i];
		//cout << cur << " "  << pr << "\n";
		if (in[cur] >= in[pr] && out[cur] <= out[pr]) {
			mn = min(mn, mnn[v][i] + d[u]);	
		} else {
			mn = min(mn, get(u, up[v][i - 1], pr));
			break;
		}
	}
	return mn;
}
 
const void solve(/*Armashka*/) {
	cin >> n >> s >> k >> e;
	for (int i = 1; i < n; ++ i) {
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		edge[i] = {u, v};		
	}
	for (int i = 1; i <= n; ++ i) dp[i] = inf;
	for (int i = 1; i <= s; ++ i) {
		ll x; cin >> x;
		sel[x] = 1;
	}
	dfs(e, -1);
	//for (int i = 1; i <= n; cout << dp[i] << " ", ++ i);
	for (int i = 1; i <= 25; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			up[j][i] = up[up[j][i - 1]][i - 1];
			mnn[j][i] = min(mnn[j][i - 1], mnn[up[j][i - 1]][i - 1]);
		}
	}
	for (int i = 1; i <= k; ++ i) {
		ll id, start;                                
		cin >> id >> start;
		ll a = edge[id].ft, b = edge[id].sd;
		if (h[a] < h[b]) swap(a, b);
		if (in[a] > in[start] || out[a] < out[start]) {
			cout << "escaped\n";
			continue;
		} 		
		
		ll res = get(start, start, a);
		if (res == inf) cout << "oo\n";
		else cout << res << "\n";
	}
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt --) {                                                
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 16 ms 24028 KB Output is correct
3 Correct 21 ms 24056 KB Output is correct
4 Correct 20 ms 24048 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 16 ms 24028 KB Output is correct
3 Correct 21 ms 24056 KB Output is correct
4 Correct 20 ms 24048 KB Output is correct
5 Correct 17 ms 24452 KB Output is correct
6 Correct 14 ms 24392 KB Output is correct
7 Correct 13 ms 24464 KB Output is correct
8 Correct 12 ms 24380 KB Output is correct
9 Correct 20 ms 24392 KB Output is correct
10 Correct 17 ms 24464 KB Output is correct
11 Correct 13 ms 24496 KB Output is correct
12 Correct 19 ms 24380 KB Output is correct
13 Correct 17 ms 24396 KB Output is correct
14 Correct 18 ms 24432 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 82760 KB Output is correct
2 Correct 238 ms 82660 KB Output is correct
3 Correct 261 ms 82816 KB Output is correct
4 Correct 233 ms 84744 KB Output is correct
5 Correct 225 ms 84816 KB Output is correct
6 Correct 372 ms 87080 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 16 ms 24028 KB Output is correct
3 Correct 21 ms 24056 KB Output is correct
4 Correct 20 ms 24048 KB Output is correct
5 Correct 17 ms 24452 KB Output is correct
6 Correct 14 ms 24392 KB Output is correct
7 Correct 13 ms 24464 KB Output is correct
8 Correct 12 ms 24380 KB Output is correct
9 Correct 20 ms 24392 KB Output is correct
10 Correct 17 ms 24464 KB Output is correct
11 Correct 13 ms 24496 KB Output is correct
12 Correct 19 ms 24380 KB Output is correct
13 Correct 17 ms 24396 KB Output is correct
14 Correct 18 ms 24432 KB Output is correct
15 Correct 206 ms 82760 KB Output is correct
16 Correct 238 ms 82660 KB Output is correct
17 Correct 261 ms 82816 KB Output is correct
18 Correct 233 ms 84744 KB Output is correct
19 Correct 225 ms 84816 KB Output is correct
20 Correct 372 ms 87080 KB Output is correct
21 Correct 246 ms 85316 KB Output is correct
22 Correct 228 ms 85144 KB Output is correct
23 Correct 240 ms 85352 KB Output is correct
24 Correct 251 ms 87480 KB Output is correct
25 Correct 286 ms 90548 KB Output is correct
26 Correct 191 ms 85660 KB Output is correct
27 Correct 225 ms 85568 KB Output is correct
28 Correct 256 ms 85780 KB Output is correct
29 Correct 267 ms 87160 KB Output is correct
30 Correct 370 ms 88868 KB Output is correct
31 Correct 233 ms 86168 KB Output is correct
32 Correct 204 ms 86144 KB Output is correct
33 Correct 221 ms 86340 KB Output is correct
34 Correct 273 ms 88232 KB Output is correct
35 Correct 305 ms 91232 KB Output is correct
36 Correct 291 ms 88192 KB Output is correct