Submission #846725

#	Time	Username	Problem	Language	Result	Execution time	Memory
846725		TahirAliyev	Valley (BOI19_valley)	C++17	100 / 100	382 ms	64388 KiB

valley

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e17
#define pii pair<int, int>

const int MAX = 1e5 + 5;
const int LOGMAX = 20;
int n, s, q, e;

struct DATA{
    ll dest = 0, dist = 0, ans = oo;
};

vector<pii> g[MAX];
DATA par[LOGMAX][MAX];
ll mindist[MAX];
vector<pii> edges;
bool isShop[MAX];
int timeIn[MAX], timeOut[MAX];

int t = 1;
void dfs(int node, int p){
    timeIn[node] = t++;
    par[0][node].dest = p;
    if(isShop[node]) par[0][node].ans = 0;
    for(pii to : g[node]){
        if(to.first == p) continue;
        par[0][to.first].dist = to.second;
        dfs(to.first, node);
        par[0][node].ans = min(par[0][to.first].ans + to.second, par[0][node].ans);
    }
    timeOut[node] = t++;
}

bool isAnc(int u, int v){
    return (timeIn[u] <= timeIn[v]) && (timeOut[u] >= timeOut[v]);
}

ll lift(int u, int v){
    ll d = 0;
    ll res = oo;
    for(int j = LOGMAX - 1; j >= 0; j --){
        if(!isAnc(par[j][u].dest, v)){
            res = min(res, par[j][u].ans + d);
            d += par[j][u].dist;
            u = par[j][u].dest;
        }
    }
    return min(res, d + par[0][u].ans);
}

int main(){
    cin >> n >> s >> q >> e;
    for(int i = 1; i <= n - 1; i++){
        int u, v, a; cin >> u >> v >> a;
        g[u].push_back({v, a});
        g[v].push_back({u, a});
        edges.push_back({u, v});
    }
    for(int i = 1; i <= s; i++){
        int a; cin >> a;
        isShop[a] = 1;
    }
    dfs(e, e);
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            int m = par[j - 1][i].dest;
            par[j][i].dest = par[j - 1][m].dest;
            par[j][i].dist = par[j - 1][i].dist + par[j - 1][m].dist;
            par[j][i].ans = min(par[j - 1][i].ans, par[j - 1][m].ans + par[j - 1][i].dist);
        }
    }
    while(q--){
        int p, node; cin >> p >> node;
        int u = edges[p - 1].first;
        int v = edges[p - 1].second;
        if(!(isAnc(u, node) && isAnc(v, node))){
            cout << "escaped\n";
            continue;
        }
        if(isAnc(v, u)){
            swap(u, v);
        }
        if(lift(node, u) >= oo){
            cout << "oo\n"; 
        }
        else{
            cout << lift(node, u) << '\n';
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41