Submission #459604

#	Time	Username	Problem	Language	Result	Execution time	Memory
459604		Ozy	Valley (BOI19_valley)	C++17	100 / 100	280 ms	47224 KiB

valley

#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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41