Submission #123015

#	Time	Username	Problem	Language	Result	Execution time	Memory
123015		model_code	Valley (BOI19_valley)	C++17	100 / 100	551 ms	39788 KiB

valley

#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];
const int K = 17;
ll st[K][N];
int par[K][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;
        par[0][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;
vl path;
const int W = 300;
int up_by_w[N];
void opti(int u, int p = -1){
    while(st[0][u] != e && shop_dist[st[0][u]] >= shop_dist[u]){
        int w = up_by_w[st[0][u]];
        if(w != e && shop_dist[w] >= shop_dist[u])
            st[0][u] = w;
        else
            st[0][u] = st[0][st[0][u]];
    }
    up_by_w[u] = st[0][u];
    for(int i = 0; i < W; ++i)
        up_by_w[u] = st[0][up_by_w[u]];
    for(int i = 0; i < sz(adj[u]); ++i){
        int v = adj[u][i];
        if(v == p) continue;
        st[0][v] = u;
        opti(v,u);
    }
}
void prep_st(){
    st[0][e] = e;
    opti(e);
    for(int s = 1; s < K; ++s)
        for(int u = 1; u <= n; ++u)
            st[s][u] = st[s-1][st[s-1][u]];
}
vpii edges;
int get_block(int id){
    int u,v;
    tie(u,v) = edges[id-1];
    return depth[u] > depth[v] ? u : v;
}
void prep_lca(){
    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";
    int v = u;
    for(int s = K-1; s >= 0; --s)
        if(depth[st[s][v]] >= depth[block])
            v = st[s][v];
    if(shop_dist[v] == INF)
        return "oo";
    return to_string(shop_dist[v]+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_st();
    prep_lca();
    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);
        _();
    }

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