oj.uz

Submission #467455

# Submission time Handle Problem Language Result Execution time Memory
467455 2021-08-23T04:03:40 Z izhang05 Valley (BOI19_valley) C++17
100 / 100
 262 ms 42004 KB 
#include <bits/stdc++.h>

using namespace std;

//#define DEBUG
void setIO(const string &name) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.exceptions(istream::failbit);
#ifdef LOCAL
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
    freopen((name + ".out").c_str(), "w", stderr);
#endif
}

const int inf = 0x3f3f3f3f, mod = 1e9 + 7, maxn = 1e5 + 5, maxs = 20;
const long long INFL = 0x3f3f3f3f3f3f3f3f;

vector<pair<int, int>> adj[maxn];
pair<int, int> edge[maxn];

int up[maxn][maxs], depth[maxn], n, tin[maxn], tout[maxn], t;
long long dist[maxn], dp[maxn], val[maxn][maxs];
bool shop[maxn];

long long jmp(int x, int d) {
    long long res = INFL;
    for (int i = 0; i < maxs; i++) {
        if ((d >> i) & 1) {
            res = min(res, val[x][i]);
            x = up[x][i];
        }
    }
    return res;
}

void dfs(int c = 0, int p = -1, int de = 0, long long di = 0) {
    up[c][0] = p;
    depth[c] = de;
    dist[c] = di;
    tin[c] = t++;
    if (shop[c]) {
        dp[c] = -di;
    }
    for (auto &i : adj[c]) {
        if (i.first != p) {
            dfs(i.first, c, de + 1, di + i.second);
            if (dp[i.first] != INFL) {
                dp[c] = min(dp[c], dp[i.first] + 2 * i.second);
            }
        }
    }
    tout[c] = t;
    val[c][0] = dp[c];
}

void build() {
    for (int i = 1; i < maxs; ++i) {
        for (int j = 0; j < n; ++j) {
            if (up[j][i - 1] == -1) {
                up[j][i] = -1;
            } else {
                val[j][i] = min(val[j][i - 1], val[up[j][i - 1]][i - 1]);
                up[j][i] = up[up[j][i - 1]][i - 1];
            }
        }
    }
}


int main() {
    setIO("2");
    memset(dp, 0x3f, sizeof(dp));
    memset(dist, 0x3f, sizeof(dist));
    int s, q, e;
    cin >> n >> s >> q >> e;
    --e;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
        edge[i] = {a, b};
    }
    for (int i = 0; i < s; ++i) {
        int c;
        cin >> c;
        --c;
        shop[c] = true;
    }
    memset(val, 0x3f, sizeof(val));
    dfs(e);
    build();
    while (q--) {
        int road, u;
        cin >> road >> u;
        --road, --u;
        int l = (depth[edge[road].first] > depth[edge[road].second] ? edge[road].first : edge[road].second);
        if (!(tin[u] >= tin[l] && tout[u] <= tout[l])) { // u is not in subtree of l
            cout << "escaped" << "\n";
            continue;
        }
        long long sol = jmp(u, depth[u] - depth[l] + 1);
        if (sol == INFL) {
            cout << "oo" << "\n";
        } else {
            cout << sol + dist[u] << "\n";
        }
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20044 KB Output is correct
2 Correct 16 ms 20036 KB Output is correct
3 Correct 14 ms 20036 KB Output is correct
4 Correct 14 ms 19980 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20044 KB Output is correct
2 Correct 16 ms 20036 KB Output is correct
3 Correct 14 ms 20036 KB Output is correct
4 Correct 14 ms 19980 KB Output is correct
5 Correct 12 ms 19996 KB Output is correct
6 Correct 12 ms 20044 KB Output is correct
7 Correct 12 ms 20044 KB Output is correct
8 Correct 11 ms 20036 KB Output is correct
9 Correct 11 ms 19992 KB Output is correct
10 Correct 12 ms 20044 KB Output is correct
11 Correct 11 ms 20044 KB Output is correct
12 Correct 12 ms 20044 KB Output is correct
13 Correct 11 ms 19992 KB Output is correct
14 Correct 11 ms 20044 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 38084 KB Output is correct
2 Correct 224 ms 37824 KB Output is correct
3 Correct 231 ms 37768 KB Output is correct
4 Correct 218 ms 39540 KB Output is correct
5 Correct 237 ms 39628 KB Output is correct
6 Correct 256 ms 41496 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20044 KB Output is correct
2 Correct 16 ms 20036 KB Output is correct
3 Correct 14 ms 20036 KB Output is correct
4 Correct 14 ms 19980 KB Output is correct
5 Correct 12 ms 19996 KB Output is correct
6 Correct 12 ms 20044 KB Output is correct
7 Correct 12 ms 20044 KB Output is correct
8 Correct 11 ms 20036 KB Output is correct
9 Correct 11 ms 19992 KB Output is correct
10 Correct 12 ms 20044 KB Output is correct
11 Correct 11 ms 20044 KB Output is correct
12 Correct 12 ms 20044 KB Output is correct
13 Correct 11 ms 19992 KB Output is correct
14 Correct 11 ms 20044 KB Output is correct
15 Correct 160 ms 38084 KB Output is correct
16 Correct 224 ms 37824 KB Output is correct
17 Correct 231 ms 37768 KB Output is correct
18 Correct 218 ms 39540 KB Output is correct
19 Correct 237 ms 39628 KB Output is correct
20 Correct 256 ms 41496 KB Output is correct
21 Correct 141 ms 37460 KB Output is correct
22 Correct 173 ms 37128 KB Output is correct
23 Correct 199 ms 37080 KB Output is correct
24 Correct 249 ms 39148 KB Output is correct
25 Correct 208 ms 42004 KB Output is correct
26 Correct 172 ms 37648 KB Output is correct
27 Correct 151 ms 37300 KB Output is correct
28 Correct 201 ms 37248 KB Output is correct
29 Correct 238 ms 38580 KB Output is correct
30 Correct 262 ms 39964 KB Output is correct
31 Correct 163 ms 37652 KB Output is correct
32 Correct 168 ms 37316 KB Output is correct
33 Correct 188 ms 37444 KB Output is correct
34 Correct 236 ms 39152 KB Output is correct
35 Correct 191 ms 41848 KB Output is correct
36 Correct 191 ms 39252 KB Output is correct