oj.uz

Submission #385835

# Submission time Handle Problem Language Result Execution time Memory
385835 2021-04-05T05:42:10 Z JerryLiu06 Editor (BOI15_edi) C++11
0 / 100
 25 ms 11896 KB 
#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]) if (NXT.f != P) 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 - 1], 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 = 0; 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 j = 20; j >= 0; j--) if (LEN & (1 << j)) { ans = min(ans, liftDP[Y][j]); Y = liftVert[Y][j]; }
 
        cout << ans + dist[X] << "\n"; 
    }
}

Compilation message

edi.cpp: In function 'void DFS1(int, int)':
edi.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]) if (NXT.f != P) DP[X] = min(DP[X], DP[NXT.f]); out[X] = timer - 1;
      |     ^~
edi.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]) if (NXT.f != P) DP[X] = min(DP[X], DP[NXT.f]); out[X] = timer - 1;
      |                                     ^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2796 KB Expected integer, but "oo" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 10092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 11896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2796 KB Expected integer, but "oo" found
2 Halted 0 ms 0 KB -