Submission #1282857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282857		dhuyyyy	Valley (BOI19_valley)	C++20	100 / 100	159 ms	25648 KiB

valley

 #include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e5+5;
const ll INF = 1e18;
const int MOD = 1e9+7;

int n, x, s, q, e, u, v, c, timer, R;

//segment
int t[N * 4];

//HLD
int tin[N], ind[N], depth[N], sz[N], heavy[N], chain[N], par[N];

//DP
int dp[N];

//tree
int sumw[N], numshop[N];
bool shop[N];
ii edge[N];
vector <ii> adj[N];

void update(int id,int l,int r,int pos,int val){
    if (r < pos || l > pos) return;
    if (l == r){
        t[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    t[id] = min(t[id * 2],t[id * 2 + 1]);
}
int getMin(int id,int l,int r,int u,int v){
    if (r < u || l > v) return INF;
    if (u <= l && r <= v) return t[id];
    int mid = (l + r) >> 1;
    int t1 = getMin(id*2,l,mid,u,v);
    int t2 = getMin(id*2+1,mid+1,r,u,v);
    return min(t1,t2);
}
void getSize(int u,int p){
    sz[u] = 1;
    for (ii it : adj[u]){
        if (it.fi == p) continue;
        depth[it.fi] = depth[u] + 1;
        par[it.fi] = u;
        sumw[it.fi] = sumw[u] + it.se;
        getSize(it.fi,u);
        numshop[u] += numshop[it.fi];
        sz[u] += sz[it.fi];
        if (sz[heavy[u]] < sz[it.fi]){
            heavy[u] = it.fi;
        }
    }
}
void getChain(int u,int p){
    tin[u] = ++timer;
    ind[timer] = u;
    if (!heavy[u]) return;
    chain[heavy[u]] = chain[u];
    getChain(heavy[u],u);
    for (ii it : adj[u]){
        if (it.fi == p || it.fi == heavy[u]) continue;
        chain[it.fi] = it.fi;
        getChain(it.fi,u);
    }
}
int LCA(int u,int v){
    while (chain[u] != chain[v]){
        if (depth[chain[u]] < depth[chain[v]]) swap(u,v);
        u = par[chain[u]];
    }
    if (depth[u] > depth[v]) swap(u,v);
    return u;
}
int getDepth(int u,int v){
    return depth[u] + depth[v] - 2 * depth[LCA(u,v)];
}
int getDist(int u,int v){
    int res = 0;
    while (chain[u] != chain[v]){
        if (depth[chain[u]] < depth[chain[v]]) swap(u,v);
        res += sumw[u] - sumw[par[chain[u]]];
        u = par[chain[u]];
    }
    if (depth[u] > depth[v]) swap(u,v);
    res += sumw[v] - sumw[u];
    return res;
}
void DP(int u,int p){
    dp[u] = (shop[u] ? 0 : INF);
    for (ii it : adj[u]){
        if (it.fi == p) continue;
        DP(it.fi,u);
        dp[u] = min(dp[u],dp[it.fi] + it.se);
    }
}
int getMinDist(int u,int v){
    int res = INF;
    while (chain[u] != chain[v]){
        if (depth[chain[u]] < depth[chain[v]]) swap(u,v);
        res = min(res,getMin(1,1,timer,tin[chain[u]],tin[u]));
        u = par[chain[u]];
    }
    if (depth[u] > depth[v]) swap(u,v);
    res = min(res,getMin(1,1,timer,tin[u],tin[v]));
    return res;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++){
        cin >> u >> v >> c;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
        edge[i] = {u,v};
    }
    for (int i = 1; i <= s; i++){
        cin >> x;
        shop[x] = 1;
        numshop[x] = 1;
    }
    chain[e] = e;
    getSize(e,0);
    getChain(e,0);
    DP(e,0);
    for (int i = 1; i <= n; i++){
        update(1,1,timer,tin[i],dp[i] - sumw[i]);
//        cout << tin[i] << ' ';
    }
//    cout << '\n';
    for (int i = 1; i < n; i++){
        u = edge[i].fi;
        v = edge[i].se;
        if (depth[u] > depth[v]) swap(edge[i].fi,edge[i].se);
    }
    while (q--){
        cin >> u >> R;
        u = edge[u].se;
        if (depth[R] != depth[u] + getDepth(u,R)) cout << "escaped" << '\n';
        else{
            if (numshop[u] == 0) cout << "oo" << '\n';
            else{
                cout << sumw[R] + getMinDist(R,u) << '\n';
            }
        }
    }
    return 0;
}

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