Submission #543774

#	Time	Username	Problem	Language	Result	Execution time	Memory
543774		ddy888	Valley (BOI19_valley)	C++17	100 / 100	222 ms	44108 KiB

valley

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b) {return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b) {return (b > a) ? a = b, 1 : 0;}

const int INF = 1e18;
int N, S, Q, E;
struct edge{int u,v,c;}; vector<edge> edges;
vector<pi> adj[100010];
int shop[100010];
int dist[100010], depth[100010], pre[100010], post[100010], timer = 1;
int magic[100010];

void dfs(int x, int p) {
    pre[x] = timer++;
    for (auto i: adj[x]) {
        if (i.fi == p) continue;
        depth[i.fi] = depth[x] + 1;
        dist[i.fi] = dist[x] + i.si;
        dfs(i.fi, x);
    }
    post[x] = timer - 1;
}

void dp(int x, int p) {     
    for (auto i: adj[x]) {
        if (i.fi == p) continue;
        dp(i.fi, x);
        chmin(magic[x], magic[i.fi]);
    }
}

struct node {
    int st, e, m, v;
    node *l, *r;
    node (int _st, int _e) {
        st = _st; e = _e; m = (st + e)/2;
        v = 0;
        if (st != e) {
            l = new node(st, m);
            r = new node(m + 1, e);
        }
    }
    void up(int x, int nv) {
        if (st == e) {v = nv; return;}
        if (x > m) r -> up(x, nv);
        if (x <= m) l -> up(x, nv);
        v = min(l->v, r->v);
    }
    int rmq(int x, int y) {
        if (st == x and e == y) return v;
        if (x > m) return r -> rmq(x, y);
        if (y <= m) return l -> rmq(x, y);
        return min(l->rmq(x, m), r->rmq(m+1, y));
    }
} *seg = new node(1, 100010);

struct HLD {
    vector<int> parent,heavy, head, pos;
    int idx;
    void init(int X) {
        parent.resize(X);
        heavy.resize(X, -1); // child at end of heavy path
        head.resize(X); // head of heavy path
        pos.resize(X); // position in segtree
        idx = 1;
        
        dfs(E);
        decompose(E, E);
    }
    int dfs(int x) {
        int sz = 1;
        int max_sz = 0;
        for (auto it: adj[x]) {
            if (it.fi == parent[x]) continue;
            parent[it.fi] = x;
            int cur_sz = dfs(it.fi);
            sz += cur_sz;
            if (cur_sz > max_sz) {
                max_sz = cur_sz;
                heavy[x] = it.fi;
            }
        }
        return sz;
    }
    
    void decompose(int x, int h) {
        head[x] = h, pos[x] = idx++;
        seg->up(pos[x], magic[x]);
        // debug(x, head[x], pos[x], magic[x]);
        if (heavy[x] != -1) decompose(heavy[x], h);
        for (auto it: adj[x]) {
            if (it.fi == parent[x] || it.fi == heavy[x]) continue;
            decompose(it.fi, it.fi);
        }
    }

    int query(int a, int b) {
        int res = INF;
        for (; head[a] != head[b]; b = parent[head[b]]) { 
            if (depth[head[a]] > depth[head[b]]) swap(a, b);
            chmin(res, seg->rmq(pos[head[b]], pos[b]));
        }
        if (a == b) return min(res, seg->rmq(pos[a], pos[a]));
        if (depth[a] > depth[b]) swap(a, b);
        chmin(res, seg->rmq(pos[a], pos[b]));
        return res;
    }
};

signed main() {
    fast;
    cin >> N >> S >> Q >> E;
    edges.resize(N + 1);
    for (int i = 1; i < N; ++i) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
        edges[i] = {u, v, c};
    }
    for (int i = 1; i <= S; ++i) {
        int x; cin >> x;
        shop[x] = 1;
    }
    dfs(E, E); 
    for (int i = 1; i <= N; ++i) {
        magic[i] = INF;
        if (shop[i]) magic[i] = dist[i];
    }
    dp(E, E);
    for (int i = 1; i <= N; ++i) if (magic[i] != INF) magic[i] -= 2 * dist[i];
    HLD hld;
    hld.init(N + 10);
    while (Q--) {
        int x, r; cin >> x >> r;
        int a = edges[x].u, b = edges[x].v;
        if (depth[a] > depth[b]) swap(a, b);
        if (pre[b] <= pre[r] && post[b] >= post[r]) { 
            int ans = hld.query(b, r);
            if (ans == INF) cout << "oo\n";
            else cout << ans + dist[r] << '\n';
        } else cout << "escaped\n";
    }   
    return 0;
}

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