oj.uz

답안 #491855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491855 2021-12-04T19:39:41 Z codr0 Valley (BOI19_valley) C++14
100 / 100
 275 ms 60720 KB 
// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cerr<<#x<<" : "<<x<<'\n'
#define MOD(x) if(x>=M) x-=M; if(x<0) x+=M;
 
using namespace std;
const int N=1e5+4;
const int Lg=22;
const int INF=1e14+100;
int par[N][Lg];
int K[N],hw[N],h[N],st[N],en[N],Tme;
int dp[N][Lg];
vector<int> adj[N];
vector<int> W[N];
int n,s,q,e;
    
    bool bit(int i,int j){
    	return ((j>>i)&1);
	}
    
    void pre(){
		FOR(i,0,N-1) K[i]=INF;
		FOR(i,0,N-1) FOR(j,0,Lg-1) dp[i][j]=INF;  
	}
    
    void dfs(int v,int p){
    	par[v][0]=p;
    	st[v]=Tme++;
    	FOR(i,0,SZ(adj[v])-1){
    		int u=adj[v][i];
    		int w=W[v][i];
    		if(u!=p){
    			hw[u]=hw[v]+w;
    			h[u]=h[v]+1;
    			dfs(u,v);
    			K[v]=min(K[v],K[u]+w);
			}
		}
		en[v]=Tme++;
	}
	
	void FILL(){
		FOR(j,1,Lg-1) FOR(i,1,n) par[i][j]=par[par[i][j-1]][j-1];
		
		FOR(i,1,n) dp[i][0]=K[i];
		FOR(j,1,Lg-1)
			FOR(i,1,n){
				dp[i][j]=min(dp[i][j-1],(hw[i]-hw[par[i][j-1]]+dp[par[i][j-1]][j-1]));
			}
	}
    
    int ans(int v,int X){
    	X++;
    	int rt=INF;
    	int dist=0;
    	FOR(i,0,21){
    		if(bit(i,X)){
    			rt=min(rt,dist+dp[v][i]);
    			dist+=(hw[v]-hw[par[v][i]]);
    			v=par[v][i];
			}
		}
		return rt;
	}
    
	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	pre();
	cin>>n>>s>>q>>e;
	vector<pair<int,int>> M;
	FOR(i,1,n-1){
		int u,v,w;
		cin>>u>>v>>w;
		M.pb({u,v});
		adj[u].pb(v);
		W[u].pb(w);
		adj[v].pb(u);
		W[v].pb(w);
	}
	FOR(i,1,s){
		int x0; cin>>x0; K[x0]=0;
	}
	dfs(e,0);
	FILL();
	FOR(i,1,q){
		int E,V;
		cin>>E>>V;
		int u=M[E-1].F;
		int v=M[E-1].S;
		if(st[v]<st[u]) swap(u,v);
		if(st[V]>=st[v]&&en[V]<=en[v]){
			int ot=ans(V,h[V]-h[v]);
			if(ot>=INF) cout<<"oo\n";
			else cout<<ot<<'\n';
		}else{
			cout<<"escaped\n";
		}
	}
	
	return 0;
    }

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23072 KB Output is correct
2 Correct 15 ms 23116 KB Output is correct
3 Correct 16 ms 23116 KB Output is correct
4 Correct 13 ms 23116 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23072 KB Output is correct
2 Correct 15 ms 23116 KB Output is correct
3 Correct 16 ms 23116 KB Output is correct
4 Correct 13 ms 23116 KB Output is correct
5 Correct 12 ms 23244 KB Output is correct
6 Correct 12 ms 23272 KB Output is correct
7 Correct 11 ms 23348 KB Output is correct
8 Correct 12 ms 23244 KB Output is correct
9 Correct 11 ms 23244 KB Output is correct
10 Correct 12 ms 23344 KB Output is correct
11 Correct 12 ms 23300 KB Output is correct
12 Correct 13 ms 23244 KB Output is correct
13 Correct 12 ms 23244 KB Output is correct
14 Correct 12 ms 23340 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 53768 KB Output is correct
2 Correct 220 ms 52848 KB Output is correct
3 Correct 215 ms 52728 KB Output is correct
4 Correct 248 ms 54688 KB Output is correct
5 Correct 249 ms 54496 KB Output is correct
6 Correct 275 ms 56156 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23072 KB Output is correct
2 Correct 15 ms 23116 KB Output is correct
3 Correct 16 ms 23116 KB Output is correct
4 Correct 13 ms 23116 KB Output is correct
5 Correct 12 ms 23244 KB Output is correct
6 Correct 12 ms 23272 KB Output is correct
7 Correct 11 ms 23348 KB Output is correct
8 Correct 12 ms 23244 KB Output is correct
9 Correct 11 ms 23244 KB Output is correct
10 Correct 12 ms 23344 KB Output is correct
11 Correct 12 ms 23300 KB Output is correct
12 Correct 13 ms 23244 KB Output is correct
13 Correct 12 ms 23244 KB Output is correct
14 Correct 12 ms 23340 KB Output is correct
15 Correct 227 ms 53768 KB Output is correct
16 Correct 220 ms 52848 KB Output is correct
17 Correct 215 ms 52728 KB Output is correct
18 Correct 248 ms 54688 KB Output is correct
19 Correct 249 ms 54496 KB Output is correct
20 Correct 275 ms 56156 KB Output is correct
21 Correct 188 ms 56804 KB Output is correct
22 Correct 209 ms 56116 KB Output is correct
23 Correct 230 ms 55984 KB Output is correct
24 Correct 248 ms 57992 KB Output is correct
25 Correct 253 ms 60720 KB Output is correct
26 Correct 195 ms 56804 KB Output is correct
27 Correct 205 ms 56316 KB Output is correct
28 Correct 217 ms 56076 KB Output is correct
29 Correct 242 ms 57392 KB Output is correct
30 Correct 272 ms 58708 KB Output is correct
31 Correct 199 ms 56888 KB Output is correct
32 Correct 248 ms 56480 KB Output is correct
33 Correct 225 ms 56240 KB Output is correct
34 Correct 250 ms 57904 KB Output is correct
35 Correct 264 ms 60596 KB Output is correct
36 Correct 221 ms 58488 KB Output is correct