oj.uz

답안 #918457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918457 2024-01-29T20:59:30 Z AlphaMale06 Valley (BOI19_valley) C++17
100 / 100
 294 ms 98492 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long
 
const int N = 100010;
vector<pair<int, int>> adj[N];
int n, s, q, e;
int h[N], cl[N], tin[N], tout[N];
int dist[N];
vector<pair<pair<int, int>, int>> edges;
int p[17][N];
bool isp[N];
int timer=-1;
int cst[N];
vector<int> sps;
vector<vector<int>> precalc;
 
void dfs(int v, int par){
	if(isp[v])dist[v]=0;
	h[v]=h[par]+1;
	p[0][v]=par;
	for(int i=1; i<=16; i++){
		p[i][v]=p[i-1][p[i-1][v]];
	}
	tin[v]=++timer;
	for(auto to : adj[v]){
		if(to.F!=par){
			dfs(to.F, v);
			dist[v]=min(dist[v], dist[to.F]+to.S);
		}
	}
	tout[v]=timer;
}
 
int anc(int a, int b){
	int ret=a;
	for(int i=0; i<17; i++){
		if(b&(1<<i)){
			ret=p[i][ret];
		}
	}
	return ret;
}
 
 
 
void solve(){
	cin >> n >> s >> q >> e;
	for(int i=0; i< n-1; i++){
		int x, y, z;
		cin >> x >> y >> z;
		edges.pb({{x, y}, z});
		adj[x].pb({y, z});
		adj[y].pb({x, z});
	}
	for(int i=0; i<=n; i++)dist[i]=1e18;
	for(int i=0; i< s; i++){
		int x;
		cin >> x;
		sps.pb(x);
		isp[x]=1;
	}
	dfs(e, 0);
	tin[0]=0; tout[0]=1e9;
	for(auto & p : edges){
		if(h[p.F.F]>h[p.F.S])swap(p.F.F, p.F.S);
		cst[p.F.S]=p.S;
	}
	int sq=300;
	precalc.pb({});
	for(int i=1; i<=n; i++){
		vector<int> prec;
		if(h[i]%sq==0){
			int x=i;
			int mn=dist[x];
			prec.pb(mn);
			int pth=0;
			while(x!=e){
				pth+=cst[x];
				x=p[0][x];
				mn=min(mn, dist[x]+pth);
				prec.pb(mn);
			}
		}
		precalc.pb(prec);
	}
	while(q--){
		int ind, v;
		cin >> ind >> v;
		pair<pair<int, int>, int> edge = edges[ind-1];
		if(h[edge.F.S]>h[v]){
			cout << "escaped\n";
			continue;
		}
		int str=anc(v, h[v]-h[edge.F.S]);
		if(str==edge.F.S){
			if(dist[str]==1e18){
				cout << "oo\n";
				continue;
			}
			int mn=dist[v];
			int pth=0;
			while(mn>0 && v!=str){
				if(precalc[v].size() && h[v]-h[str]>100){
					mn=min(mn, pth+precalc[v][h[v]-h[str]]);
					break;
				}
				pth+=cst[v];
				if(mn<=pth)break;
				v=p[0][v];
				mn=min(mn, pth+dist[v]);	
			}
			cout << mn << '\n';
		}
		else cout << "escaped\n";
	}
}
 
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 5 ms 20716 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 5 ms 20716 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20656 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 20828 KB Output is correct
9 Correct 5 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 5 ms 20828 KB Output is correct
12 Correct 5 ms 20828 KB Output is correct
13 Correct 5 ms 20864 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 39524 KB Output is correct
2 Correct 106 ms 39676 KB Output is correct
3 Correct 113 ms 39572 KB Output is correct
4 Correct 193 ms 53756 KB Output is correct
5 Correct 160 ms 53484 KB Output is correct
6 Correct 242 ms 98492 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 5 ms 20828 KB Output is correct
3 Correct 6 ms 20828 KB Output is correct
4 Correct 5 ms 20716 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20656 KB Output is correct
7 Correct 5 ms 21080 KB Output is correct
8 Correct 5 ms 20828 KB Output is correct
9 Correct 5 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 5 ms 20828 KB Output is correct
12 Correct 5 ms 20828 KB Output is correct
13 Correct 5 ms 20864 KB Output is correct
14 Correct 5 ms 20828 KB Output is correct
15 Correct 118 ms 39524 KB Output is correct
16 Correct 106 ms 39676 KB Output is correct
17 Correct 113 ms 39572 KB Output is correct
18 Correct 193 ms 53756 KB Output is correct
19 Correct 160 ms 53484 KB Output is correct
20 Correct 242 ms 98492 KB Output is correct
21 Correct 102 ms 36096 KB Output is correct
22 Correct 101 ms 35728 KB Output is correct
23 Correct 105 ms 37940 KB Output is correct
24 Correct 172 ms 59128 KB Output is correct
25 Correct 289 ms 97464 KB Output is correct
26 Correct 96 ms 36324 KB Output is correct
27 Correct 104 ms 36088 KB Output is correct
28 Correct 123 ms 37620 KB Output is correct
29 Correct 177 ms 53240 KB Output is correct
30 Correct 294 ms 85288 KB Output is correct
31 Correct 103 ms 35836 KB Output is correct
32 Correct 101 ms 36732 KB Output is correct
33 Correct 132 ms 38652 KB Output is correct
34 Correct 208 ms 75524 KB Output is correct
35 Correct 268 ms 96068 KB Output is correct
36 Correct 161 ms 54664 KB Output is correct