Submission #123016

#TimeUsernameProblemLanguageResultExecution timeMemory
123016model_codeValley (BOI19_valley)C++17
100 / 100
826 ms28716 KiB
////!pragma
//const int N = 1e5+5;
//vl adj[N],cost[N];
//ll depth[N],root_dist[N],shop_dist[N],dir_par[N];
//bool is_shop[N];
//void dfs(int u, int p = -1){
//    shop_dist[u] = is_shop[u] ? 0 : INF;
//    for(int i = 0; i < sz(adj[u]); ++i){
//        int v = adj[u][i];
//        if(v == p) continue;
//        dir_par[v] = u;
//        depth[v] = depth[u]+1;
//        root_dist[v] = root_dist[u]+cost[u][i];
//        dfs(v,u);
//        shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i]);
//    }
//}
//int n,e;
//const int W = 150;
//ll cheat_up[N], cheat_w[N];
//vl rdfs_order;
//void opti(int u, int p = -1){
//    while(cheat_up[u] != e && shop_dist[cheat_up[u]] >= shop_dist[u])
//        cheat_up[u] = cheat_up[cheat_up[u]];
//    for(int i = 0; i < sz(adj[u]); ++i){
//        int v = adj[u][i];
//        if(v == p) continue;
//        cheat_up[v] = u;
//        opti(v,u);
//    }
//}
//void prep_cheat(){
//    cheat_up[e] = e;
//    opti(e);
//    for(int i = 1; i <= n; ++i){
//        cheat_w[i] = cheat_up[i];
//        for(int j = 0; j < W; ++j)
//            cheat_w[j] = cheat_up[cheat_w[j]];
//    }
//}
//vpii edges;
//int get_block(int id){
//    int u,v;
//    tie(u,v) = edges[id-1];
//    return depth[u] > depth[v] ? u : v;
//}
//const int K = 17;
//int par[K][N];
//void lca_prep(){
//    for(int u = 1; u <= n; ++u)
//        par[0][u] = dir_par[u];
//    for(int s = 1; s < K; ++s)
//        for(int u = 1; u <= n; ++u)
//            par[s][u] = par[s-1][par[s-1][u]];
//}
//int get_lca(int u, int v){
//    if(depth[u] < depth[v])
//        swap(u,v);
//    for(int k = K-1; k >= 0; --k)
//        if(depth[par[k][u]] >= depth[v])
//            u = par[k][u];
//    if(u == v)
//        return u;
//    for(int k = K-1; k >= 0; --k)
//        if(par[k][u] != par[k][v]){
//            u = par[k][u];
//            v = par[k][v];
//        }
//    return par[0][u];
//}
//string solve(int u, int block){
//    //first part: correct: can we escape?
//    int lca = get_lca(u,block);
//    if(lca != block)
//        return "escaped";
//    //watch(u);
//    //watch(block);
//    //watch(lca);
//    //second part: cheating, TODO: find a test to break this
//    ll ans = INF;
//    for(int v = u; ;){
//        if(depth[v] < depth[block])
//            break;
//        if(shop_dist[v] != INF)
//            ans = min(ans,shop_dist[v]);
//        if(depth[cheat_w[v]] >= depth[block]){
//            v = cheat_w[v];
//        }
//        else
//            v = cheat_up[v];
//    }
//    if(ans == INF) return "oo";
//    return to_string(ans+root_dist[u]);
//}
//void _(){
//    int s,q;
//    cin >> n >> s >> q >> e;
//    for(int i = 0; i < n-1; ++i){
//        int a,b,w;
//        cin >> a >> b >> w;
//        adj[a].pb(b);
//        adj[b].pb(a);
//        cost[a].pb(w);
//        cost[b].pb(w);
//        edges.pb({a,b});
//    }
//    for(int i = 0; i < s; ++i){
//        int u;
//        cin >> u;
//        is_shop[u] = true;
//    }
//    depth[e] = 1;
//    dfs(e);
//    for(int i = 1; i <= n; ++i)
//        if(shop_dist[i] != INF)
//            shop_dist[i] -= root_dist[i];
//    prep_cheat();
//    lca_prep();
//    //watch(root_dist[3]);
//    //watch(shop_dist[3]);
//    //watch(root_dist[5]);
//    for(int i = 0; i < q; ++i){
//        int id,u;
//        cin >> id >> u;
//        int block = get_block(id);
//        print(solve(u,block));
//    }
//}
#pragma GCC optimize("Ofast")
#include <stack>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const ll INF = ll(2e18) + 666;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 void print(T x, string end = "\n"){
    cout << x << end;
}
//!pragma
const int N = 1e5+5;
vl adj[N],cost[N];
ll depth[N],root_dist[N],shop_dist[N],dir_par[N];
bool is_shop[N];
void dfs(int u, int p = -1){
    shop_dist[u] = is_shop[u] ? 0 : INF;
    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        if(v == p) continue;
        dir_par[v] = u;
        depth[v] = depth[u]+1;
        root_dist[v] = root_dist[u]+cost[u][i];
        dfs(v,u);
        shop_dist[u] = min(shop_dist[u],shop_dist[v]+cost[u][i]);
    }
}
int n,e;
const int W = 250;
ll cheat_up[N], cheat_w[N];
int up_by_w[N];
void opti(int u, int p = -1){
    while(cheat_up[u] != e && shop_dist[cheat_up[u]] >= shop_dist[u]){
        int w = up_by_w[cheat_up[u]];
        if(w != e && shop_dist[w] >= shop_dist[u])
            cheat_up[u] = w;
        else
            cheat_up[u] = cheat_up[cheat_up[u]];
    }
    up_by_w[u] = cheat_up[u];
    for(int i = 0; i < W; ++i)
        up_by_w[u] = cheat_up[up_by_w[u]];
    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        if(v == p) continue;
        cheat_up[v] = u;
        opti(v,u);
    }
}
void prep_cheat(){
    cheat_up[e] = e;
    opti(e);
    for(int i = 1; i <= n; ++i){
        cheat_w[i] = cheat_up[i];
        for(int j = 0; j < W; ++j)
            cheat_w[i] = cheat_up[cheat_w[i]];
    }
}
vpii edges;
int get_block(int id){
    int u,v;
    tie(u,v) = edges[id-1];
    return depth[u] > depth[v] ? u : v;
}
const int K = 17;
int par[K][N];
void lca_prep(){
    for(int u = 1; u <= n; ++u)
        par[0][u] = dir_par[u];
    for(int s = 1; s < K; ++s)
        for(int u = 1; u <= n; ++u)
            par[s][u] = par[s-1][par[s-1][u]];
}
int get_lca(int u, int v){
    if(depth[u] < depth[v])
        swap(u,v);
    for(int k = K-1; k >= 0; --k)
        if(depth[par[k][u]] >= depth[v])
            u = par[k][u];
    if(u == v)
        return u;
    for(int k = K-1; k >= 0; --k)
        if(par[k][u] != par[k][v]){
            u = par[k][u];
            v = par[k][v];
        }
    return par[0][u];
}
string solve(int u, int block){
    int lca = get_lca(u,block);
    if(lca != block)
        return "escaped";
    ll ans = INF;
    for(int v = u; ;){
        if(depth[v] < depth[block])
            break;
        while(depth[cheat_w[v]] >= depth[block]){
            //cerr << "called: " << depth[v] << ' ' << depth[cheat_w[v]] << '\n';
            v = cheat_w[v];
        }
        if(shop_dist[v] != INF)
            ans = min(ans,shop_dist[v]);
        v = cheat_up[v];
    }
    if(ans == INF) return "oo";
    return to_string(ans+root_dist[u]);
}
void _(){
    int s,q;
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; ++i){
        int a,b,w;
        cin >> a >> b >> w;
        adj[a].pb(b);
        adj[b].pb(a);
        cost[a].pb(w);
        cost[b].pb(w);
        edges.pb({a,b});
    }
    for(int i = 0; i < s; ++i){
        int u;
        cin >> u;
        is_shop[u] = true;
    }
    depth[e] = 1;
    dfs(e);
    for(int i = 1; i <= n; ++i)
        if(shop_dist[i] != INF)
            shop_dist[i] -= root_dist[i];
    prep_cheat();
    lca_prep();
    //cerr << "prep done\n";
    //watch(root_dist[3]);
    //watch(shop_dist[3]);
    //watch(root_dist[5]);
    for(int i = 0; i < q; ++i){
        int id,u;
        cin >> id >> u;
        int block = get_block(id);
        print(solve(u,block));
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        _();
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...