Submission #391808

#	Time	Username	Problem	Language	Result	Execution time	Memory
391808		JerryLiu06	Valley (BOI19_valley)	C++11	100 / 100	277 ms	45120 KiB

valley

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, ll> pil;
 
#define pb push_back
 
#define f first
#define s second
 
int N, S, Q, E; int U[100010], V[100010]; vector<pil> adj[100010]; bool isShop[100010];
 
int timer, in[100010], out[100010], depth[100010]; ll dist[100010], DP[100010]; 
 
int liftVert[100010][21]; ll liftDP[100010][21]; const ll INF = 1e18 + 10;
 
bool isAnc(int A, int B) { return in[A] <= in[B] && out[B] <= out[A]; }
 
void DFS1(int X, int P) {
    in[X] = timer++; if (isShop[X]) DP[X] = dist[X]; else DP[X] = INF; 
    
    for (pil NXT : adj[X]) if (NXT.f != P) { 
        depth[NXT.f] = depth[X] + 1; dist[NXT.f] = dist[X] + NXT.s; DFS1(NXT.f, X); 
        
        DP[X] = min(DP[X], DP[NXT.f]);
    }
    liftVert[X][0] = P; out[X] = timer - 1;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> N >> S >> Q >> E;
 
    for (int i = 1; i <= N - 1; i++) { 
        int A, B; ll W; cin >> A >> B >> W;
 
        U[i] = A, V[i] = B; adj[A].pb({B, W}); adj[B].pb({A, W}); 
    }
    for (int i = 0; i < S; i++) { int X; cin >> X; isShop[X] = true; }
 
    DFS1(E, 0); for (int i = 1; i <= N; i++) DP[i] -= 2 * dist[i], liftDP[i][0] = DP[i];
    
    for (int i = 0; i <= 20; i++) liftDP[0][i] = INF;
    
    for (int j = 1; j <= 20; j++) for (int i = 1; i <= N; i++) {
        
        liftVert[i][j] = liftVert[liftVert[i][j - 1]][j - 1];
        liftDP[i][j] = min(liftDP[i][j - 1], liftDP[liftVert[i][j - 1]][j - 1]);
    }
    for (int i = 0; i < Q; i++) { 
        int I, X; cin >> I >> X; int LOW = (depth[U[I]] > depth[V[I]]) ? U[I] : V[I];
        
        if (!isAnc(LOW, X)) { cout << "escaped" << "\n"; continue; }
 
        if (DP[LOW] + 2 * dist[LOW] == INF) { cout << "oo" << "\n"; continue; }
 
        int LEN = depth[X] - depth[LOW]; ll ans = INF; int Y = X;
 
        for (int j = 20; j >= 0; j--) if (LEN & (1 << j)) { ans = min(ans, liftDP[Y][j]); Y = liftVert[Y][j]; }
 
        cout << min(ans, DP[LOW]) + dist[X] << "\n"; 
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41