Submission #659495

#	Time	Username	Problem	Language	Result	Execution time	Memory
659495		Ronin13	Valley (BOI19_valley)	C++14	100 / 100	393 ms	40244 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 2e5 + 1;
vector <vector <ll> > t(nmax);
vector <vector <pii> > g(nmax);
vector <vector <int> > path(nmax);
vector <int> lead(nmax);
vector <int> p(nmax);
vector <int> sz(nmax);
vector <ll> d(nmax);
vector <ll> dp(nmax, 2e18);
vector <bool> shop(nmax);
vector <int> pp(nmax);
vector <int> in(nmax);
int timer = 1;
void dfs(int v, int e = 0){
    sz[v] = 1;
    p[v] = e;
    in[v] = timer++;
    for(auto x : g[v]){
        int to = x.f;
        ll len = x.s;
        if(to == e) continue;
        d[to] = d[v] + len;
        dfs(to, v);
        dp[v] = min(dp[v], dp[to] + len);
        sz[v] += sz[to];
    }
    if(shop[v]) dp[v] = 0;
}

void decompose(int v, int head, int e = 0){
    path[head].pb(v);
    pp[v] = path[head].size();
    lead[v] = head;
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        if(2 * sz[to] >= sz[v]) decompose(to, head, v);
        else decompose(to, to, v);
    }

}

void update(int v, int l, int r, int pos, int ind, ll val){
    if(pos > r || pos < l) return;
    if(l == r){
        t[ind][v] = min((ll)1e18, val);
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, ind, val);
    update(2 * v + 1, m + 1, r, pos, ind, val);
    t[ind][v] = min(t[ind][2 * v], t[ind][2 * v + 1]);
}

ll get(int v, int l, int r, int st, int fin, int ind){
    if(l > fin || r < st) return 1e18;
    if(l >= st && r <=  fin) {
        return t[ind][v];
    }
    int m = (l + r) / 2;
    return min(get(2 * v, l, m, st, fin, ind),
               get(2 * v + 1, m + 1, r, st, fin, ind));
}

void build(int n){
    for(int i = 1; i <= n; i++){
        t[i].resize(path[i].size() * 4);
    }
    for(int i= 1; i <= n; i++){
        update(1, 1, path[lead[i]].size(), pp[i], lead[i], -d[i] + dp[i]);
    }
}

ll lift(ll x, ll y){
    ll ans = 1e18;
    while(lead[x] != lead[y]){
        int v = lead[x];
        ans = min(ans, get(1, 1, path[v].size(), pp[v], pp[x], v));
        x = p[v];
    }
    int v = lead[x];
    ans = min(ans, get(1, 1,  path[v].size(), pp[y], pp[x], v));
    return ans;
}

int main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    int edge[n];
    vector <pii> edges;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        ll w; cin >> w;
        edges.pb({u, v});
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for(int i = 1; i <= s; i++){
        int x; cin >> x;
        shop[x] = true;
    }
    dfs(e);
    decompose(e, e);

   /* for(int i = 1; i <= n; i++)
        cout << lead[i] << ' ';*/
    for(int i = 1; i < n; i++){
        int x = edges[i - 1].f, y = edges[i - 1].s;
        if(p[x] == y){
            edge[i] = x;
        }
        else edge[i] = y;
    }
    build(n);
    while(q--){
        int x, r; cin >> x >> r;
        int v = edge[x];
        if(in[v] > in[r] || (in[v] + sz[v] < in[r] + sz[r])) {
            cout << "escaped\n";
            continue;
        }
        ll D = lift(r, v);
        if(D == 1e18){
            cout << "oo\n";
            continue;
        }
        cout << D + d[r] << "\n";
    }
}

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