oj.uz

Submission #133187

# Submission time Handle Problem Language Result Execution time Memory
133187 2019-07-20T08:52:45 Z muradeyn Valley (BOI19_valley) C++14
100 / 100
 571 ms 47384 KB 
/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
//#define endl '\n'

using namespace std;

const int maxx = 100001 , lg = 17;

int n , m , q , ex , nxt;

int lvl[maxx] , in[maxx] , dp[maxx] , shop[maxx] , cnt[maxx];

intt dist[maxx] , table[maxx][lg] , close[maxx] , par[maxx][lg];

vector< pair<int,intt> >v[maxx] , arr;

void dfs(int s,int p) {
    dp[s] = 1;
    cnt[s] = shop[s];
    par[s][0] = p;
    in[s] = ++nxt;
    lvl[s] = lvl[p] + 1;
    for (auto to : v[s])
        if (to.F != p) dist[to.F] = dist[s] + to.S , dfs(to.F , s) , dp[s] += dp[to.F] , cnt[s] += cnt[to.F];
}

void build(int s,int p) {
    if (shop[s])close[s] = dist[s];
    else close[s] = 1000000000000000LL;
    for (auto to : v[s]) {
        if (to.F == p)continue;
        build(to.F , s);
        close[s] = min(close[s] , close[to.F]);
    }
}

int x , y , w;

int main() {
    fyck
    cin>>n>>m>>q>>ex;
    for (int i = 1;i<n;i++) {
        cin>>x>>y>>w;
        v[x].push_back({y , w});
        v[y].push_back({x , w});
        arr.push_back({x , y});
    }
    for (int i = 1;i<=m;i++)cin>>x , shop[x] = 1;
    dfs(ex , 0);
    build(ex , 0);
    for (int i = 1;i<=n;i++)close[i] -= 2 * dist[i] , table[i][0] = close[i];
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            table[i][j] = min(table[i][j - 1],table[par[i][j - 1]][j - 1]);
    int i , r;
    while (q--) {
        cin>>i>>r;
        i--;
        x = arr[i].F; y = arr[i].S;
        if (lvl[x] < lvl[y])swap(x , y);
        intt res = (in[r] >= in[x] && in[r] <= in[x] + dp[x] - 1);
        if (!res)cout<<"escaped"<<endl;
        else if (cnt[x] == 0)cout<<"oo"<<endl;
        else {
            intt res = 1000000000000000LL , re = dist[r];
            int diff = lvl[r] - lvl[x];
            for (int i = 0;i<lg;i++) {
                if ((1 << i) & diff) {
                    res = min(res , table[r][i]);
                    r = par[r][i];
                }
            }
            res = min(res , table[r][0]);
            cout<<res + re<<endl;
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2940 KB Output is correct
2 Correct 32 ms 2960 KB Output is correct
3 Correct 32 ms 2868 KB Output is correct
4 Correct 34 ms 2936 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2940 KB Output is correct
2 Correct 32 ms 2960 KB Output is correct
3 Correct 32 ms 2868 KB Output is correct
4 Correct 34 ms 2936 KB Output is correct
5 Correct 8 ms 3192 KB Output is correct
6 Correct 8 ms 3192 KB Output is correct
7 Correct 8 ms 3192 KB Output is correct
8 Correct 8 ms 3064 KB Output is correct
9 Correct 8 ms 3192 KB Output is correct
10 Correct 8 ms 3192 KB Output is correct
11 Correct 8 ms 3064 KB Output is correct
12 Correct 8 ms 3124 KB Output is correct
13 Correct 8 ms 3192 KB Output is correct
14 Correct 8 ms 3192 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 43848 KB Output is correct
2 Correct 498 ms 43656 KB Output is correct
3 Correct 517 ms 43776 KB Output is correct
4 Correct 548 ms 45272 KB Output is correct
5 Correct 527 ms 45520 KB Output is correct
6 Correct 571 ms 47288 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2940 KB Output is correct
2 Correct 32 ms 2960 KB Output is correct
3 Correct 32 ms 2868 KB Output is correct
4 Correct 34 ms 2936 KB Output is correct
5 Correct 8 ms 3192 KB Output is correct
6 Correct 8 ms 3192 KB Output is correct
7 Correct 8 ms 3192 KB Output is correct
8 Correct 8 ms 3064 KB Output is correct
9 Correct 8 ms 3192 KB Output is correct
10 Correct 8 ms 3192 KB Output is correct
11 Correct 8 ms 3064 KB Output is correct
12 Correct 8 ms 3124 KB Output is correct
13 Correct 8 ms 3192 KB Output is correct
14 Correct 8 ms 3192 KB Output is correct
15 Correct 528 ms 43848 KB Output is correct
16 Correct 498 ms 43656 KB Output is correct
17 Correct 517 ms 43776 KB Output is correct
18 Correct 548 ms 45272 KB Output is correct
19 Correct 527 ms 45520 KB Output is correct
20 Correct 571 ms 47288 KB Output is correct
21 Correct 468 ms 43172 KB Output is correct
22 Correct 491 ms 42956 KB Output is correct
23 Correct 521 ms 43272 KB Output is correct
24 Correct 518 ms 44928 KB Output is correct
25 Correct 544 ms 47384 KB Output is correct
26 Correct 486 ms 43576 KB Output is correct
27 Correct 480 ms 43192 KB Output is correct
28 Correct 504 ms 43440 KB Output is correct
29 Correct 506 ms 44640 KB Output is correct
30 Correct 546 ms 46092 KB Output is correct
31 Correct 460 ms 42340 KB Output is correct
32 Correct 494 ms 40324 KB Output is correct
33 Correct 488 ms 40476 KB Output is correct
34 Correct 540 ms 42472 KB Output is correct
35 Correct 546 ms 44952 KB Output is correct
36 Correct 548 ms 45052 KB Output is correct