Submission #386568

#	Time	Username	Problem	Language	Result	Execution time	Memory
386568		jeroenodb	Valley (BOI19_valley)	C++17	0 / 100	122 ms	30316 KiB

valley

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e17;
ll dist[mxN], ans[mxN], dp[18][mxN];
int jump[18][mxN], d[mxN];
int go(int at, int delta) {
    for(int i=0;1<<i <= delta;++i) {
        if(1<<i & delta) {
            at = jump[i][at];
        }
    }
    return at;
}
ll solve(int at, int delta) {
    if(delta==0) return ans[at];
    ll res = oo;
    int to = at;
    for(int i=0;1<<i <= delta;++i) {
        if(1<<i & delta) {
            res = min(res,dist[at]-dist[to]+dp[i][to]);
            to = jump[i][to];
        }
    }
    return res;
}
vector<pi> adj[mxN];
bitset<mxN> shop;
void dfs(int at, int from) {
    if(!shop[at]) {
        ans[at] = oo;
    }
    for(auto [to,w]: adj[at]) if(to!=from) {
        dist[to] = dist[at]+w;
        d[to] = d[at]+1;
        dfs(to,at);
        ans[at] = min(ans[at],w+ans[to]);
        jump[0][to] = at;
    }
    dp[0][at] = ans[at];
    for(auto [to,w]: adj[at]) if(to!=from) {
        dp[0][to] = min(dp[0][to], dp[0][at]+w);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k,q,root; cin >> n >> k >> q >> root; root--;
    struct edge{
        int a,b,w;
    }; vector<edge> edges(n-1);
    for(auto& e : edges) {
        cin >> e.a >> e.b >> e.w;
        e.a--;e.b--;
        adj[e.a].emplace_back(e.b,e.w);
        adj[e.b].emplace_back(e.a,e.w);
    }
    while(k--) {
        int s; cin >> s;--s;
        shop[s] = true;
    }
    jump[0][root] = root;
    dfs(root,-1);
    for(int i=1;(1<<i)<n;++i) {
        for(int j=0;j<n;++j) {
            int to = jump[i-1][j];
            jump[i][j] = jump[i-1][to];
            dp[i][j] = min(dp[i-1][j], dist[j]-dist[to] + dp[i-1][to]);
        }
    }
    while(q--) {
        int a,at; cin >> a >> at; --a,--at;
        auto& e = edges[a];
        if(d[e.a]<d[e.b]) swap(e.a,e.b);
        int delta = d[at]-d[e.a];
        int from = go(at,delta);
        if(from!=e.a) {
            cout << "escape\n";
            continue;
        }
        auto tmp = solve(at,delta);
        if(tmp==oo) cout << "oo\n";
        else cout << tmp << '\n';

    }
}

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