oj.uz

답안 #363162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363162 2021-02-05T08:02:39 Z ngpin04 Valley (BOI19_valley) C++14
100 / 100
 250 ms 42092 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;

vector <pair <int, int>> adj[N];

pair <int, int> edge[N];

long long dp[20][N];
long long mindis[N];
long long dis[N];
long long val[N];

int lca[20][N];
int h[N];
int n,s,q,t;

bool store[N];

void dfs(int u, int p)
{
    lca[0][u] = p;

    mindis[u] = (store[u]) ? dis[u] : oo;

    for (pair <int, int> to : adj[u])
    {
        int v = to.fi;
        int w = to.se;
        if (v == p)
            continue;
        h[v] = h[u] + 1;
        dis[v] = dis[u] + w;
        dfs(v, u);
        mindis[u] = min(mindis[u], mindis[v]);
    }
    val[u] = mindis[u] - 2 * dis[u];
}

void build()
{
    for (int i = 1; i <= n; i++)
    {
        int p = lca[0][i];
        dp[0][i] = (p < 0) ? oo : val[p];
    }

    for (int j = 1; j < 20; j++)
    for (int i = 1; i <= n; i++)
    {
        int p = lca[j - 1][i];
        if (p < 0)
            lca[j][i] = p, dp[j][i] = oo;
        else
            lca[j][i] = lca[j - 1][p], dp[j][i] = min(dp[j - 1][p], dp[j - 1][i]);
    }
}

pair <long long, int> jump(int u, int step)
{
    if (step < 0)
        return mp(oo, -1);

    long long res = val[u];
    for (int i = 0; i < 20; i++) if ((step >> i) & 1)
    {
        res = min(res, dp[i][u]);
        u = lca[i][u];
    }
    return mp(res, u);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> s >> q >> t;
    for (int i = 1; i < n; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;

        adj[u].push_back(mp(v, w));
        adj[v].push_back(mp(u, w));

        edge[i] = mp(u, v);
    }

    for (int i = 1; i <= s; i++)
    {
        int x;
        cin >> x;
        store[x] = true;
    }

    dfs(t, -1);

    build();

    while (q--)
    {
        int id,cur;
        cin >> id >> cur;
        int u = edge[id].fi;
        int v = edge[id].se;
        if (h[u] > h[v])
            swap(u, v);

        pair <long long, int> res = jump(cur, h[cur] - h[v]);
        if (res.se != v)
            cout << "escaped\n";
        else if (res.fi > (long long) 1e15)
            cout << "oo\n";
        else
            cout << res.fi + dis[cur] << "\n";
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Correct 5 ms 3052 KB Output is correct
3 Correct 5 ms 3052 KB Output is correct
4 Correct 6 ms 3052 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Correct 5 ms 3052 KB Output is correct
3 Correct 5 ms 3052 KB Output is correct
4 Correct 6 ms 3052 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 3 ms 3180 KB Output is correct
7 Correct 3 ms 3308 KB Output is correct
8 Correct 3 ms 3180 KB Output is correct
9 Correct 3 ms 3180 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 3 ms 3180 KB Output is correct
12 Correct 3 ms 3180 KB Output is correct
13 Correct 3 ms 3308 KB Output is correct
14 Correct 3 ms 3308 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 34436 KB Output is correct
2 Correct 155 ms 34028 KB Output is correct
3 Correct 166 ms 34056 KB Output is correct
4 Correct 187 ms 35816 KB Output is correct
5 Correct 211 ms 35820 KB Output is correct
6 Correct 232 ms 37740 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Correct 5 ms 3052 KB Output is correct
3 Correct 5 ms 3052 KB Output is correct
4 Correct 6 ms 3052 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 3 ms 3180 KB Output is correct
7 Correct 3 ms 3308 KB Output is correct
8 Correct 3 ms 3180 KB Output is correct
9 Correct 3 ms 3180 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 3 ms 3180 KB Output is correct
12 Correct 3 ms 3180 KB Output is correct
13 Correct 3 ms 3308 KB Output is correct
14 Correct 3 ms 3308 KB Output is correct
15 Correct 137 ms 34436 KB Output is correct
16 Correct 155 ms 34028 KB Output is correct
17 Correct 166 ms 34056 KB Output is correct
18 Correct 187 ms 35816 KB Output is correct
19 Correct 211 ms 35820 KB Output is correct
20 Correct 232 ms 37740 KB Output is correct
21 Correct 123 ms 34412 KB Output is correct
22 Correct 152 ms 34028 KB Output is correct
23 Correct 155 ms 33900 KB Output is correct
24 Correct 176 ms 39404 KB Output is correct
25 Correct 227 ms 42092 KB Output is correct
26 Correct 121 ms 37740 KB Output is correct
27 Correct 150 ms 37612 KB Output is correct
28 Correct 155 ms 37352 KB Output is correct
29 Correct 170 ms 38764 KB Output is correct
30 Correct 250 ms 40172 KB Output is correct
31 Correct 124 ms 37868 KB Output is correct
32 Correct 143 ms 37484 KB Output is correct
33 Correct 154 ms 37612 KB Output is correct
34 Correct 176 ms 39276 KB Output is correct
35 Correct 223 ms 41964 KB Output is correct
36 Correct 165 ms 39404 KB Output is correct