Submission #1097341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097341		Phuoc	Valley (BOI19_valley)	C++14	23 / 100	142 ms	47444 KiB

valley

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define el '\n'
#define int ll
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b) {a = b; return true;} return false;
    }
 
const ll MOD = (ll)1e9 + 7;
const int oo = (int)1e9 + 10;
const ll INF = (ll)1e18 + 9LL;
 
template <class T1, class T2>
    void add (T1 &a, T2 b) {
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
const int N = 100100;
const int LOG = 18;
 
int nVillage, nFarm, styn, nQuery;
vector <pair<int, ll> > adj [N];
bool isFarm[N];
pair <int, int> queries [N];
 
struct edge {
    int u, v; ll c;
    edge (int _u = 0, int _v = 0, ll _c = 0) {
        u = _u; v = _v; c = _c;
    }
} edges[N];
 
void init (void) {
    cin >> nVillage >> nFarm >> nQuery >> styn;
    for (int i = 1; i < nVillage; i++) {
        int u, v; ll c; cin >> u >> v >> c;
        adj[u].push_back(make_pair(v, c));
        adj[v].push_back(make_pair(u, c));
        edges[i] = edge (u, v, c);
    }
    for (int i = 1; i <= nFarm; i++) {
        int x; cin >> x; isFarm[x] = true;
    }
}
 
int fin[N], fout[N], dep[N], par[N][LOG];
ll dist[N], dp[N], minVal[N][LOG], val[N];
bool have_farm_in[N];
int tgDfs = 0;
 
void dfs (int u, int p) {
    fin[u] = ++tgDfs;
    have_farm_in[u] = isFarm[u];
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + x.se;
        par[v][0] = u;
        dfs (v, u);
        if(have_farm_in[v]) have_farm_in[u] = true;
    }
    fout[u] = tgDfs;
}
 
void calc (int u, int p) {
    dp[u] = isFarm[u] ? 0 : oo;
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        calc(v, u);
        minimize(dp[u], dp[v] + x.se);
    }
}
 
void build_val (int u, int p) {
    // if(p == 0) minVal[u][0] = dp[u] - dist[u];
    // else minVal[u][0] = min(dp[u] - dist[u], dp[p] - dist[p]);
    // for (int i = 1; i < LOG; i++) {
    //     minVal[u][i] = min(minVal[u][i - 1], minVal[par[u][i - 1]][i - 1]);
    // }    
    for (auto x : adj[u]) {
        int v = x.fi;
        if(v == p) continue;
        minVal[v][0] = min(dp[u] - dist[u], dp[v] - dist[v]);
        build_val(v, u);
    }
}
 
int getMin (int u, int diff) {
    int ans = INF;
    for (int i = 0; i < LOG; i++) {
        if(BIT(diff, i)) {
            minimize(ans, minVal[u][i]);
            u = par[u][i];
        }
    }
    return ans;
}
 
void solve (void) {
    dfs (styn, 0);
    calc (styn, 0);
    for (int j = 1; j < LOG; j++) for(int i = 1; i <= nVillage; i++) par[i][j] = par[par[i][j - 1]][j - 1];
 
    memset(minVal, oo, sizeof minVal); 
    // memset(dp, oo, sizeof dp);
    build_val(styn, 0);
    for (int j = 1; j < LOG; j++) for (int i = 1; i <= nVillage; i++) minVal[i][j] = min(minVal[i][j - 1], minVal[par[i][j - 1]][j - 1]);
 
    for (int lmao = 1; lmao <= nQuery; lmao++) {
        int ban, node; cin >> ban >> node;
        edge e = edges[ban];
        int u = e.u, v = e.v;
        if(dep[v] < dep[u]) swap(u, v); 
        if(!(fin[node] >= fin[v] && fin[node] <= fout[v])) {
            cout << "escaped" << el;
        }
        else {
            if(!have_farm_in[v]) {
                cout << "oo" << el;
                continue;
            }
            ll ans = INF;
            if(have_farm_in[node]) minimize(ans, dp[node]);
            int diff = dep[node] - dep[v];
            minimize(ans, getMin(node, diff) + dist[node]);
            cout << ans << el;
        }
    }
}
 
signed main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int ntest = 1;
 
    while (ntest--) {
        init();
        solve();
    }
}

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