oj.uz

답안 #459604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
459604 2021-08-08T18:20:28 Z Ozy Valley (BOI19_valley) C++17
100 / 100
 280 ms 47224 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define INF 1000000000000000
#define MAX 100000
#define p first
#define MIN second
#define des first
#define val second

lli n,s,q,ini,a,b,c,cont1,cont2,k,act;
pair<lli,lli> padre[20][MAX+2];
vector<pair<lli,lli> > orden;
vector<pair<lli,lli> > hijos[MAX+2];
lli pre[MAX+2], post[MAX+2],shops[MAX+2], prof[MAX+2], camino[MAX+2];

lli DFS(lli pos, lli pp, lli deep, lli dis) {

    prof[pos] = deep;
    camino[pos] = dis;
    pre[pos] = ++cont1;

    lli x,m = INF;
    for(auto h : hijos[pos]){
        if (h.des == pp) continue;
        x = DFS(h.des,pos,deep+1,dis+h.val);
        x += h.val;
        if (x < m) m = x;
    }
    post[pos] = ++cont2;

    if (shops[pos] == 1) m = 0;

    padre[0][pos].p = pp;
    if (m < INF) padre[0][pos].MIN = m-dis;
    else padre[0][pos].MIN = INF;

    return m;
}

void process(lli pos, lli pp){

    lli pot = 0;
    while (padre[pot][ padre[pot][pos].p ].p != 0) {
        padre[pot+1][pos].p = padre[pot][ padre[pot][pos].p ].p;
        padre[pot+1][pos].MIN = min(padre[pot][ padre[pot][pos].p ].MIN, padre[pot][pos].MIN);
        pot++;
    }

    for (auto h : hijos[pos]) {
        if (h.des == pp) continue;
        process(h.des,pos);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s >> q >> ini;
    orden.push_back({0,0});
    rep(i,1,n-1) {
        cin >> a >> b >> c;
        hijos[a].push_back({b,c});
        hijos[b].push_back({a,c});
        orden.push_back({a,b});
    }
    rep(i,1,s) {
        cin >> a;
        shops[a] = 1;
    }

    a = DFS(ini,0,1,0);
    process(ini,0);

    rep(i,1,q) {

        cin >> a >> c;
        b = orden[a].first;
        a = orden[a].second;
        if (prof[b] > prof[a]) swap(a,b);

        if ((pre[a] <= pre[c]) && (post[a] >= post[c])) {

            k = prof[c] - prof[b];
            lli pot = 0,m=INF;
            act = c;

            while (k > 0) {
                if (k&1) {
                    if (padre[pot][act].MIN < m) m = padre[pot][act].MIN;
                    act = padre[pot][act].p;
                }
                pot++;
                k/=2;
            }

            if (m >= INF) cout << "oo\n";
            else {
                m += camino[c];
                cout << m << "\n";
            }

        }
        else cout << "escaped\n";

    }
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 8 ms 2940 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 4 ms 3020 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 3 ms 2868 KB Output is correct
13 Correct 3 ms 3020 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 24048 KB Output is correct
2 Correct 201 ms 25520 KB Output is correct
3 Correct 190 ms 33188 KB Output is correct
4 Correct 242 ms 43208 KB Output is correct
5 Correct 203 ms 43304 KB Output is correct
6 Correct 280 ms 47024 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 8 ms 2940 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 4 ms 3020 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 3 ms 2868 KB Output is correct
13 Correct 3 ms 3020 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 147 ms 24048 KB Output is correct
16 Correct 201 ms 25520 KB Output is correct
17 Correct 190 ms 33188 KB Output is correct
18 Correct 242 ms 43208 KB Output is correct
19 Correct 203 ms 43304 KB Output is correct
20 Correct 280 ms 47024 KB Output is correct
21 Correct 128 ms 22672 KB Output is correct
22 Correct 182 ms 24416 KB Output is correct
23 Correct 180 ms 30536 KB Output is correct
24 Correct 220 ms 42044 KB Output is correct
25 Correct 255 ms 46700 KB Output is correct
26 Correct 145 ms 23160 KB Output is correct
27 Correct 150 ms 24456 KB Output is correct
28 Correct 172 ms 30852 KB Output is correct
29 Correct 210 ms 41456 KB Output is correct
30 Correct 238 ms 44996 KB Output is correct
31 Correct 153 ms 23544 KB Output is correct
32 Correct 188 ms 25008 KB Output is correct
33 Correct 207 ms 33116 KB Output is correct
34 Correct 224 ms 42860 KB Output is correct
35 Correct 254 ms 47224 KB Output is correct
36 Correct 218 ms 42716 KB Output is correct