oj.uz

답안 #431941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431941 2021-06-17T17:33:38 Z SirCovidThe19th Valley (BOI19_valley) C++14
100 / 100
 688 ms 43804 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e5+5, ml = 17;

int n, sh, q, e, tin[mx], tout[mx], cnt; 
ll d[mx], dp[mx], up[ml][mx], best[ml][mx]; bool shop[mx];
pii edges[mx]; vector<pii> adj[mx]; 

ll dfs(int node){
    tin[node] = cnt++; ll ret = ((shop[node]) ? d[node] : LLONG_MAX); 
    for (int l = 1; l < ml; l++) up[l][node] = up[l-1][up[l-1][node]];
    for (pii nxt : adj[node])
        if (nxt.f != up[0][node])
            d[nxt.f] = d[node]+nxt.s, up[0][nxt.f] = node, ret = min(ret, dfs(nxt.f));
    dp[node] = ret-d[node]*2; tout[node] = cnt-1; return ret;
}

int main() {
    cin >> n >> sh >> q >> e;
    for (int i = 1; i < n; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        edges[i] = {a, b};
    }for (int i = 0; i < sh; i++) { int a; cin >> a; shop[a] = 1; }
    dfs(e); memset(best, 0x3f, sizeof(best)); 
    for (int i = 1; i <= n; i++) best[0][i] = dp[up[0][i]]; 
    for (int l = 1; l < ml; l++)
        for (int i = 1; i <= n; i++)
            best[l][i] = min(best[l-1][i], best[l-1][up[l-1][i]]);
    while (q--){
        int i, r; cin >> i >> r; ll ans = dp[r]; int curr = r;
        int root = ((up[0][edges[i].f] == edges[i].s) ? edges[i].f : edges[i].s);
        if (!(tin[root] <= tin[r] and tout[root] >= tout[r])) cout<<"escaped"<<endl;
        else if (dp[root] >= 1e16) cout<<"oo"<<endl; 
        else{
            for (int l = ml-1; l >= 0; l--) 
                if (d[up[l][curr]] >= d[root]) 
                    ans = min(ans, best[l][curr]), curr = up[l][curr];
            cout<<ans+d[r]<<endl;
        }
    }
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16196 KB Output is correct
2 Correct 30 ms 16104 KB Output is correct
3 Correct 36 ms 16188 KB Output is correct
4 Correct 34 ms 16180 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16196 KB Output is correct
2 Correct 30 ms 16104 KB Output is correct
3 Correct 36 ms 16188 KB Output is correct
4 Correct 34 ms 16180 KB Output is correct
5 Correct 13 ms 16268 KB Output is correct
6 Correct 16 ms 16204 KB Output is correct
7 Correct 15 ms 16324 KB Output is correct
8 Correct 14 ms 16244 KB Output is correct
9 Correct 13 ms 16204 KB Output is correct
10 Correct 13 ms 16204 KB Output is correct
11 Correct 13 ms 16204 KB Output is correct
12 Correct 13 ms 16204 KB Output is correct
13 Correct 13 ms 16232 KB Output is correct
14 Correct 13 ms 16232 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 614 ms 40896 KB Output is correct
2 Correct 561 ms 40504 KB Output is correct
3 Correct 596 ms 40424 KB Output is correct
4 Correct 682 ms 41896 KB Output is correct
5 Correct 633 ms 41932 KB Output is correct
6 Correct 688 ms 43356 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16196 KB Output is correct
2 Correct 30 ms 16104 KB Output is correct
3 Correct 36 ms 16188 KB Output is correct
4 Correct 34 ms 16180 KB Output is correct
5 Correct 13 ms 16268 KB Output is correct
6 Correct 16 ms 16204 KB Output is correct
7 Correct 15 ms 16324 KB Output is correct
8 Correct 14 ms 16244 KB Output is correct
9 Correct 13 ms 16204 KB Output is correct
10 Correct 13 ms 16204 KB Output is correct
11 Correct 13 ms 16204 KB Output is correct
12 Correct 13 ms 16204 KB Output is correct
13 Correct 13 ms 16232 KB Output is correct
14 Correct 13 ms 16232 KB Output is correct
15 Correct 614 ms 40896 KB Output is correct
16 Correct 561 ms 40504 KB Output is correct
17 Correct 596 ms 40424 KB Output is correct
18 Correct 682 ms 41896 KB Output is correct
19 Correct 633 ms 41932 KB Output is correct
20 Correct 688 ms 43356 KB Output is correct
21 Correct 463 ms 40212 KB Output is correct
22 Correct 466 ms 39904 KB Output is correct
23 Correct 483 ms 39848 KB Output is correct
24 Correct 518 ms 41564 KB Output is correct
25 Correct 591 ms 43756 KB Output is correct
26 Correct 463 ms 40456 KB Output is correct
27 Correct 464 ms 39932 KB Output is correct
28 Correct 490 ms 40020 KB Output is correct
29 Correct 590 ms 41080 KB Output is correct
30 Correct 633 ms 42308 KB Output is correct
31 Correct 468 ms 40320 KB Output is correct
32 Correct 507 ms 40132 KB Output is correct
33 Correct 526 ms 40116 KB Output is correct
34 Correct 586 ms 41496 KB Output is correct
35 Correct 581 ms 43804 KB Output is correct
36 Correct 597 ms 41660 KB Output is correct