Submission #1257923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257923		limon4ick	Valley (BOI19_valley)	C++20	36 / 100	65 ms	1860 KiB

valley

/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#pragma ("reroll") */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ins insert
#define F first
#define S second
const int mod = 1e7 + 7,N = 1100;
int d[N];
int up[N][20];
vector<pair<int,int>>g[N];
int d1[N];
bool was[N];
void dfs(int v,int p,int bl1,int bl2){
    was[v] = 1;
    up[v][0] = p;
    for(int i = 1;i<20;i++) up[v][i] = up[up[v][i-1]][i-1];
    for(auto xz : g[v]){
        int to = xz.F;
        int w = xz.S;
        if(to==p || (bl1 == v && bl2 == to) || (bl2 == v && bl1 == to)) continue;
        d[to] = d[v] + 1;
        d1[to] = d1[v] + w;
        dfs(to,v,bl1,bl2);
    }
}
int lca(int a,int b){
    if(d[a]>d[b]) swap(a,b);
    int dist =d[b] - d[a];
    for(int i = 0;i<20;i++){
        if(dist & (1<<i)){
            b = up[b][i];
        }
    }
    if(a==b) return a;
    for(int i = 19;i>=0;i--){
        if(up[a][i]!=up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}
signed main(){
    //freopen("justcoding.in","r",stdin);
    //freopen("justcoding.out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,s,q,e;
    cin >> n >> s >> q >> e;
    int u1[n],v1[n];
    for(int i = 1;i<n;i++){
        int c;
        cin >> u1[i] >> v1[i] >> c;
        g[u1[i]].pb({v1[i],c});
        g[v1[i]].pb({u1[i],c});
    }
    int a[s+1];
    for(int i = 1;i<=s;i++){
        cin >> a[i];
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        dfs(r,0,u1[l],v1[l]);
        int mn = 1e18;
        if(was[e]) cout << "escaped\n";
        else{
            for(int i = 1;i<=s;i++){
                if(was[a[i]]){
                    int x = lca(a[i],r);
                    mn = min(mn,d1[r]-d1[x] + d1[a[i]]-d1[x]);
                }
            }
            if(mn==1e18) cout << "oo\n";
            else cout << mn << '\n';
        }
        for(int i = 1;i<=n;i++){
            was[i] = 0;
            d[i] = 0;
            d1[i] = 0;
            for(int j = 0;j<20;j++) up[i][j] = 0;
        }
    }
}

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