Submission #385797

#	Time	Username	Problem	Language	Result	Execution time	Memory
385797		JerryLiu06	Valley (BOI19_valley)	C++11	0 / 100	183 ms	38252 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++; 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); }

    if (isShop[X]) DP[X] = dist[X]; for (pil NXT : adj[X]) DP[X] = min(DP[X], DP[NXT.f]); out[X] = timer - 1;
}
void DFS2(int X, int P) {
    liftVert[X][0] = P; liftDP[X][0] = min(DP[X], DP[P]);

    for (int i = 1; i < 20; i++) {
        liftVert[X][i] = liftVert[liftVert[X][i - 1]][i - 1]; 
        liftDP[X][i] = min(liftDP[X][i], liftDP[liftVert[X][i - 1]][i - 1]);
    }
    for (pil NXT : adj[X]) if (NXT.f != P) DFS2(NXT.f, X);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> S >> Q >> E; for (int i = 1; i <= N; i++) DP[i] = INF;

    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]; DFS2(E, 0);

    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 i = 20; i >= 0; i--) if (LEN & (1 << i)) { ans = min(ans, liftDP[Y][i]); Y = liftVert[Y][i]; }

        cout << ans + dist[X] << "\n"; 
    }
}

Compilation message (stderr)

valley.cpp: In function 'void DFS1(int, int)':
valley.cpp:24:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |     if (isShop[X]) DP[X] = dist[X]; for (pil NXT : adj[X]) DP[X] = min(DP[X], DP[NXT.f]); out[X] = timer - 1;
      |     ^~
valley.cpp:24:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |     if (isShop[X]) DP[X] = dist[X]; for (pil NXT : adj[X]) DP[X] = min(DP[X], DP[NXT.f]); out[X] = timer - 1;
      |                                     ^~~

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