oj.uz

답안 #873780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873780 2023-11-15T18:21:58 Z hqminhuwu Valley (BOI19_valley) C++14
100 / 100
 128 ms 145792 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e17;
const ll mod = 1e9 + 7;

ll bg[N],ed[N],dp[N],dep[N],d[N],up[20][N],updp[20][N],cnt;
vector <pll> a[N],edge;
void dfs (int u, int p){
    bg[u] = ++cnt;
    for (pii k : a[u]){
        int w = k.nd, v = k.st;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        d[v] = d[u] + w;
        up[0][v] = u;
        dfs(v,u);
        dp[u] = min (dp[u],dp[v] + w);
    }
    ed[u] = cnt;
}

void dfs1 (int u, int p){
    for (pii k : a[u]){
        int w = k.nd, v = k.st;
        if (v == p) continue;
        updp[0][v] = dp[u] - d[u];
        dfs1(v,u);
    }
}

bool anc (int u, int v){
    return (bg[u] <= bg[v]) && (ed[u] >= ed[v]);
}


ll jump (int u, int v) {
    ll ans = oo,i;
    ford (i,18,0) 
    if (v & (1 << i)){
        ans = min(ans, updp[i][u]);
        u = up[i][u];
    }
    return ans;
}

ll n,s,q,e,i,j,u,v,w;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s >> q >> e;
    forf (i,1,n) {
        cin >> u >> v >> w;
        edge.pb({u, v});
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    forr (j,0,18)
    forr (i,1,n)
        updp[j][i] = oo;
    forr (i,1,n)
        dp[i] = oo;
    forr (i,1,s)
        cin >> u, dp[u] = 0;
    dfs(e,e);
    dfs1(e,e);
    forr (j,1,18)
    forr (i,1,n)
        up[j][i] = up[j - 1][up[j - 1][i]],
        updp[j][i] = min(updp[j - 1][i],updp[j - 1][up[j - 1][i]]);
    forf (i,0,n - 1)
    if (d[edge[i].st] < d[edge[i].nd])
        swap(edge[i].st, edge[i].nd);
    while (q--){
        cin >> i >> u;
        int v = edge[i - 1].st;
        if (!anc(v,u)){
            cout << "escaped\n";
            continue;
        }
        if (dp[v] == oo){
            cout << "oo\n";
            continue;
        }

        cout << min (d[u] + jump(u,dep[u] - dep[v]),dp[u]) << "\n";
    }
    return 0;
}
/*



*/

Compilation message

valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:42:13: warning: unused variable 'w' [-Wunused-variable]
   42 |         int w = k.nd, v = k.st;
      |             ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 95320 KB Output is correct
2 Correct 13 ms 95060 KB Output is correct
3 Correct 12 ms 95064 KB Output is correct
4 Correct 13 ms 95192 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 95320 KB Output is correct
2 Correct 13 ms 95060 KB Output is correct
3 Correct 12 ms 95064 KB Output is correct
4 Correct 13 ms 95192 KB Output is correct
5 Correct 12 ms 95068 KB Output is correct
6 Correct 12 ms 95068 KB Output is correct
7 Correct 12 ms 95068 KB Output is correct
8 Correct 12 ms 95064 KB Output is correct
9 Correct 12 ms 95064 KB Output is correct
10 Correct 13 ms 95112 KB Output is correct
11 Correct 12 ms 95068 KB Output is correct
12 Correct 12 ms 95068 KB Output is correct
13 Correct 12 ms 95140 KB Output is correct
14 Correct 12 ms 95320 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 135612 KB Output is correct
2 Correct 91 ms 136124 KB Output is correct
3 Correct 98 ms 135612 KB Output is correct
4 Correct 114 ms 138432 KB Output is correct
5 Correct 98 ms 138684 KB Output is correct
6 Correct 125 ms 141244 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 95320 KB Output is correct
2 Correct 13 ms 95060 KB Output is correct
3 Correct 12 ms 95064 KB Output is correct
4 Correct 13 ms 95192 KB Output is correct
5 Correct 12 ms 95068 KB Output is correct
6 Correct 12 ms 95068 KB Output is correct
7 Correct 12 ms 95068 KB Output is correct
8 Correct 12 ms 95064 KB Output is correct
9 Correct 12 ms 95064 KB Output is correct
10 Correct 13 ms 95112 KB Output is correct
11 Correct 12 ms 95068 KB Output is correct
12 Correct 12 ms 95068 KB Output is correct
13 Correct 12 ms 95140 KB Output is correct
14 Correct 12 ms 95320 KB Output is correct
15 Correct 99 ms 135612 KB Output is correct
16 Correct 91 ms 136124 KB Output is correct
17 Correct 98 ms 135612 KB Output is correct
18 Correct 114 ms 138432 KB Output is correct
19 Correct 98 ms 138684 KB Output is correct
20 Correct 125 ms 141244 KB Output is correct
21 Correct 76 ms 139796 KB Output is correct
22 Correct 83 ms 139316 KB Output is correct
23 Correct 85 ms 139452 KB Output is correct
24 Correct 94 ms 142048 KB Output is correct
25 Correct 122 ms 145792 KB Output is correct
26 Correct 77 ms 139528 KB Output is correct
27 Correct 84 ms 139304 KB Output is correct
28 Correct 92 ms 139452 KB Output is correct
29 Correct 107 ms 141276 KB Output is correct
30 Correct 121 ms 143292 KB Output is correct
31 Correct 79 ms 139608 KB Output is correct
32 Correct 103 ms 139476 KB Output is correct
33 Correct 90 ms 139712 KB Output is correct
34 Correct 128 ms 142008 KB Output is correct
35 Correct 110 ms 144832 KB Output is correct
36 Correct 106 ms 142012 KB Output is correct