oj.uz

답안 #705625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705625 2023-03-04T20:05:04 Z bane Valley (BOI19_valley) C++17
100 / 100
 270 ms 59576 KB 
/*
 * prep: 4.3
 */

#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define ll long long 
using i64 = long long;
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
int N = (int)1e5 + 1;
int n,s,q,e;
int t  = 0;
ll inf = (ll)1e15;
vector<i64> in(N), out(N), shop(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> id(N);
vector<vector<pair<int, int>>> adj(N);
vector<vector<i64>> up(N, vector<i64>(20)), dp2(N, vector<i64>(20));
void DepthFirstSearch(int u, int p){
	up[u][0] = p;
	x[u]=inf;
	in[u]=++t;
    if (shop[u]) {
        x[u] = d[u];
    }
    for (auto [v, w] : adj[u])  { 
        if (v != p) {
            d[v] = d[u] + w;
            DepthFirstSearch(v, u);
            x[u] = min(x[u], x[v]);
        }
    }
    out[u]=t - 1;
    dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
    dp2[u][0] = dp[u];
}

bool inside(int u, int from){
	return (in[u]<=in[from] && out[u] >= out[from]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s >> q >> e;
	for (int i=0 ; i < n - 1; i++){
		int a,b,w;
		cin >> a >> b >> w;
		adj[a].pb(mp(b,w));
		adj[b].pb(mp(a,w));
		id[i+1] = mp(a,b);
	}
	for(int i = 0; i < s; ++i){
		int j;cin >> j;
		shop[j]=1;
	}
	DepthFirstSearch(e,e);
	for (int i = 1; i<20; i++){
		for (int j = 1; j<=n; j++){
			up[j][i] = up[up[j][i-1]][i-1];
			dp2[j][i] = min(dp2[j][i-1], dp2[up[j][i-1]][i-1]);
		}
	}
	while(q--){
		int i, r;
        cin >> i >> r;
        auto [u, v] = id[i];
        if (inside(u, v)) {
            swap(u, v);
        }
        if (!inside(u, r)) {
            cout << "escaped\n";
        } else {
            i64 best = dp[u], dd = d[r];
            for (int b = 19; b >= 0; b--) {
                if (inside(u, up[r][b])) {
                    best = min(best, dp2[r][b]);
                    r = up[r][b];
                }
            }
            if (best == inf) {
                cout << "oo\n";
            } else {
                cout << dd + best << '\n';
            }
        }
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47412 KB Output is correct
2 Correct 28 ms 47356 KB Output is correct
3 Correct 31 ms 47436 KB Output is correct
4 Correct 33 ms 47444 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47412 KB Output is correct
2 Correct 28 ms 47356 KB Output is correct
3 Correct 31 ms 47436 KB Output is correct
4 Correct 33 ms 47444 KB Output is correct
5 Correct 32 ms 47328 KB Output is correct
6 Correct 28 ms 47256 KB Output is correct
7 Correct 29 ms 47444 KB Output is correct
8 Correct 30 ms 47316 KB Output is correct
9 Correct 30 ms 47356 KB Output is correct
10 Correct 28 ms 47376 KB Output is correct
11 Correct 28 ms 47360 KB Output is correct
12 Correct 28 ms 47276 KB Output is correct
13 Correct 32 ms 47360 KB Output is correct
14 Correct 28 ms 47400 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 52272 KB Output is correct
2 Correct 206 ms 51940 KB Output is correct
3 Correct 216 ms 51980 KB Output is correct
4 Correct 268 ms 53760 KB Output is correct
5 Correct 203 ms 53576 KB Output is correct
6 Correct 270 ms 55776 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 47412 KB Output is correct
2 Correct 28 ms 47356 KB Output is correct
3 Correct 31 ms 47436 KB Output is correct
4 Correct 33 ms 47444 KB Output is correct
5 Correct 32 ms 47328 KB Output is correct
6 Correct 28 ms 47256 KB Output is correct
7 Correct 29 ms 47444 KB Output is correct
8 Correct 30 ms 47316 KB Output is correct
9 Correct 30 ms 47356 KB Output is correct
10 Correct 28 ms 47376 KB Output is correct
11 Correct 28 ms 47360 KB Output is correct
12 Correct 28 ms 47276 KB Output is correct
13 Correct 32 ms 47360 KB Output is correct
14 Correct 28 ms 47400 KB Output is correct
15 Correct 200 ms 52272 KB Output is correct
16 Correct 206 ms 51940 KB Output is correct
17 Correct 216 ms 51980 KB Output is correct
18 Correct 268 ms 53760 KB Output is correct
19 Correct 203 ms 53576 KB Output is correct
20 Correct 270 ms 55776 KB Output is correct
21 Correct 189 ms 55104 KB Output is correct
22 Correct 184 ms 54772 KB Output is correct
23 Correct 208 ms 54852 KB Output is correct
24 Correct 248 ms 56788 KB Output is correct
25 Correct 241 ms 59576 KB Output is correct
26 Correct 185 ms 55236 KB Output is correct
27 Correct 193 ms 54840 KB Output is correct
28 Correct 202 ms 54860 KB Output is correct
29 Correct 239 ms 56140 KB Output is correct
30 Correct 267 ms 57608 KB Output is correct
31 Correct 193 ms 55336 KB Output is correct
32 Correct 207 ms 54860 KB Output is correct
33 Correct 209 ms 54904 KB Output is correct
34 Correct 247 ms 56732 KB Output is correct
35 Correct 247 ms 59412 KB Output is correct
36 Correct 232 ms 56888 KB Output is correct