Submission #529321

#	Time	Username	Problem	Language	Result	Execution time	Memory
529321		OttoTheDino	Valley (BOI19_valley)	C++17	100 / 100	169 ms	29316 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (ll i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const ll mx = 1e5;
const ll inf = 5e18;
ll d[mx+1], ans[mx+1], sp[mx+1];
vi a;
vii qs[mx+1], adj[mx+1];
ii roads[mx+1];
ll b[mx+1], seg[4*mx+1];

void upd (ll x, ll val, ll l, ll r, ll id) {
    if (l==r) {
        seg[id] = val;
        return;
    }
    
    ll mid = (l+r)/2;
    if (x<=mid) upd (x, val, l, mid, 2*id);
    else upd (x, val, mid+1, r, 2*id+1);

    seg[id] = min(seg[2*id], seg[2*id+1]);
}

ll query (ll l, ll r, ll bl, ll br, ll id) {
    if (l==bl && r==br) return seg[id];
    ll mid = (bl+br)/2;
    if (r<=mid) return query(l, r, bl, mid, 2*id);
    else if (l>mid) return query (l, r, mid+1, br, 2*id+1);
    return min(query (l, mid, bl, mid, 2*id), query(mid+1, r, mid+1, br, 2*id+1));
}

void dfs (ll u, ll p) {
    if (!sp[u]) b[u] = inf;
    for (ii vw : adj[u]) {
        ll v = vw.fi, w = vw.se;
        if (v==p) continue;
        d[v] = d[u]+1;
        dfs (v, u);
        if (b[v]<inf) b[u] = min(b[u], b[v]+w);
    }
}

void dfs2 (ll u, ll p, ll D) {
    a.pb(u);
    if (b[u]==inf) upd (a.size()-1, inf, 1, mx, 1);
    else upd (a.size()-1, b[u]-D, 1, mx, 1);

    for (ii q : qs[u]) {
        ll i = q.fi, id = q.se;
        if (max(d[roads[i].fi], d[roads[i].se]) <= d[u]&& a[d[roads[i].fi]]==roads[i].fi && a[d[roads[i].se]]==roads[i].se) {
            ll res = query (max(d[roads[i].fi], d[roads[i].se]), d[u], 1, mx, 1);


            if (res==inf) ans[id] = -2;
            else ans[id] = res+D;
        }
        else ans[id] = -1;
    }

    for (ii vw : adj[u]) {
        ll v = vw.fi, w = vw.se;
        if (v==p) continue;
        dfs2 (v, u, D+w);
    }

    a.pop_back();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, s, q, e; cin >> n >> s >> q >> e;
    rep (i,1,n-1) {
        ll u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        roads[i] = {u,v};
    }

    rep (i,1,s) {
        ll x; cin >> x;
        sp[x] = 1;
    }

    rep (i,1,q) {
        ll I, R; cin >> I >> R;
        qs[R].pb({I,i});
    }

    a.pb(0);
    d[e] = 1;
    dfs (e,-1);
    dfs2 (e,-1,0);

    rep (i,1,q) {
        if (ans[i]==-1) cout << "escaped\n";
        else if (ans[i]==-2) cout << "oo\n";
        else cout << ans[i] << "\n";
    }

    return 0;
}

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