Submission #1016772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016772		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	241 ms	67004 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=1e5+5, mod = 1e9+7, inf = 1e18, L = 18;

int n, s, q, e, timer=0;
vector<ii> adj[N];
vector<ii> edges;
int in[N], out[N], d[N], r[N];
int up[N][L], len[N][L], mn[N][L];
bool shop[N];
vector<int> seg;

void update(int node, int l, int r, int idx, int val) {
    if(l>idx || r<idx) return;
    if(l==r) {
        seg[node] += val;
        return;
    }

    int mid = (l+r)>>1;
    update(node<<1, l, mid, idx, val); update(node<<1|1, mid+1, r, idx, val);
    seg[node] = seg[node<<1]+seg[node<<1|1];
}

int get(int node, int l, int r, int ql, int qr) {
    if(l>qr || r<ql) return 0;
    if(ql<=l && r<=qr) return seg[node];

    int mid = (l+r)>>1;
    return get(node<<1, l, mid, ql, qr) + get(node<<1|1, mid+1, r, ql, qr);
}

void dfs(int u, int p, int w_) {
    in[u] = ++timer;
    d[u] = d[p]+1;

    // cout << u << ":" << len[u][1] << " " << up[u][0] << " " << len[up[u][0]][0]<< '\n';

    up[u][0] = p;
    for (int i=1; i<L; i++) up[u][i] = up[up[u][i-1]][i-1];

    len[u][0] = w_;
    for (int i=1; i<L; i++) len[u][i] = len[u][i-1] + len[up[u][i-1]][i-1];

    int res = inf;
    for (ii it: adj[u]) {
        int v = it.fi, w = it.se;
        if(v!=p) {
            dfs(v, u, w);
            res = min(res, w+r[v]);
        }
    }

    if(shop[u]) res = 0;
    r[u] = res;
    
    out[u] = timer;
}

void dfs_mn(int u, int p) {
    mn[u][0] = min(r[u], len[u][0]+r[p]);
    for (int i=1; i<L; i++) mn[u][i] = min(mn[u][i-1], mn[up[u][i-1]][i-1]+len[u][i-1]);

    for (ii it: adj[u]) {
        int v = it.fi, w = it.se;
        if(v!=p) {
            dfs_mn(v, u);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    edges.pb({0, 0});
    for (int i=1; i<n; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edges.pb({u, v});
    }

    for (int i=0; i<s; i++) {
        int c; cin >> c;
        shop[c] = 1;
    }
    d[0] = -1;
    dfs(e, 0, 0);

    r[0] = inf;
    dfs_mn(e, 0);

    seg.assign(4*n+5, 0);

    while(q--) {
        int road, vill; cin >> road >> vill;
        int u = edges[road].fi, v = edges[road].se;
        if(up[u][0]==v) swap(u, v);
        update(1, 1, n, in[v], 1); 
        if(out[v]+1<=n) update(1, 1, n, out[v]+1, -1);
        int res = get(1, 1, n, 1, in[vill]);
        update(1, 1, n, in[v], -1);
        if(out[v]+1<=n) update(1, 1, n, out[v]+1, 1);
        if(res==0) {
            cout << "escaped\n";
            continue;
        }

        int k = d[vill]-d[v];

        int ans = r[vill], dist = 0;

        for (int i=0; i<L; i++) {
            if ((1<<i)&k) {
                ans = min(ans, mn[vill][i]+dist);
                dist += len[vill][i];
                vill = up[vill][i];
            }
        }
        if(ans>=inf) cout << "oo\n";
        else cout << ans << '\n';
    }
    // cout << "##########\n";
    // cout << mn[1][0];
}

Compilation message (stderr)

valley.cpp: In function 'void dfs_mn(long long int, long long int)':
valley.cpp:73:24: warning: unused variable 'w' [-Wunused-variable]
   73 |         int v = it.fi, w = it.se;
      |                        ^

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