oj.uz

Submission #440654

# Submission time Handle Problem Language Result Execution time Memory
440654 2021-07-02T16:21:43 Z BeanZ Valley (BOI19_valley) C++14
100 / 100
 318 ms 59348 KB 
// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
struct viet{
    ll u, v, w;
};
vector<viet> E;
ll dp[N][lg + 1], par[N][lg + 1], dep[N], a[N], dep2[N];
vector<pair<ll, ll>> node[N];
void dfs2(ll u, ll p){
    for (int i = 1; i <= lg; i++){
        dp[u][i] = min(dp[u][i - 1], dp[par[u][i - 1]][i - 1]);
    }
    for (auto j : node[u]){
        if (j.first == p) continue;
        dfs2(j.first, u);
    }
}
void dfs(ll u, ll p){
    for (int i = 1; i <= lg; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    dp[u][0] = 1e18;
    for (auto j : node[u]){
        if (j.first == p) continue;
        par[j.first][0] = u;
        dep[j.first] = dep[u] + j.second;
        dep2[j.first] = dep2[u] + 1;
        dfs(j.first, u);
        dp[u][0] = min(dp[u][0], dp[j.first][0] + dep[j.first] + j.second - dep[u]);
    }
    if (a[u]) dp[u][0] = -dep[u];
}
ll check(ll u, ll v){
    ll dist = dep2[v] - dep2[u];
    if (dist < 0) return 0;
    for (int i = 0; i <= lg; i++){
        if (dist & (1 << i)){
            v = par[v][i];
        }
    }
    if (v == u) return 1;
    else return 0;
}
ll get(ll u, ll v){
    ll dist = dep2[u] - dep2[v];
    ll res = 1e18;
    ll dd = dep[u];
    for (int i = 0; i <= lg; i++){
        if (dist & (1 << i)){
            res = min(res, dd + dp[u][i]);
            u = par[u][i];
        }
    }
    res = min(res, dd + dp[u][0]);
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, s, q, e;
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        E.push_back({u, v, w});
        node[u].push_back({v, w});
        node[v].push_back({u, w});
    }
    for (int i = 1; i <= s; i++){
        ll x;
        cin >> x;
        a[x] = 1;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= lg; j++){
            dp[i][j] = 1e18;
        }
    }
    dfs(e, e);
    dfs2(e, e);
    while (q--){
        ll u, v;
        cin >> v >> u;
        ll n1 = E[v - 1].u;
        ll n2 = E[v - 1].v;
        if (dep[n1] < dep[n2]) swap(n1, n2);
        if (!check(n1, u)) cout << "escaped" << endl;
        else {
            ll x = get(u, n1);
            if (x > 1e17) cout << "oo" << endl;
            else cout << x << endl;
        }
    }
}
/*
Ans:

Out:
*/

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2820 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2764 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2820 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2764 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 4 ms 3132 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 52956 KB Output is correct
2 Correct 239 ms 52884 KB Output is correct
3 Correct 262 ms 53064 KB Output is correct
4 Correct 300 ms 55664 KB Output is correct
5 Correct 264 ms 55676 KB Output is correct
6 Correct 318 ms 58732 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2820 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2764 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 4 ms 3132 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 216 ms 52956 KB Output is correct
16 Correct 239 ms 52884 KB Output is correct
17 Correct 262 ms 53064 KB Output is correct
18 Correct 300 ms 55664 KB Output is correct
19 Correct 264 ms 55676 KB Output is correct
20 Correct 318 ms 58732 KB Output is correct
21 Correct 197 ms 51736 KB Output is correct
22 Correct 223 ms 51544 KB Output is correct
23 Correct 249 ms 51952 KB Output is correct
24 Correct 290 ms 54676 KB Output is correct
25 Correct 306 ms 58732 KB Output is correct
26 Correct 194 ms 52036 KB Output is correct
27 Correct 226 ms 52008 KB Output is correct
28 Correct 245 ms 52048 KB Output is correct
29 Correct 279 ms 54044 KB Output is correct
30 Correct 316 ms 56200 KB Output is correct
31 Correct 201 ms 52592 KB Output is correct
32 Correct 224 ms 52412 KB Output is correct
33 Correct 248 ms 52720 KB Output is correct
34 Correct 299 ms 55296 KB Output is correct
35 Correct 308 ms 59348 KB Output is correct
36 Correct 270 ms 55364 KB Output is correct