Submission #1149773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149773		arkanefury	Valley (BOI19_valley)	C++20	59 / 100	267 ms	50104 KiB

valley

#include <bits/stdc++.h>  
#define pb push_back  
using namespace std; 
#define F first
#define S second
#define int long long
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)  
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)  
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);  
const int N = 1e5+150;  
int n,m,k,tt,ans,l, r, x, y, cnt, ko = 0; 
int b[N],a[N], sum, lp[N], block =  620, d[N], c[N], up[N][21], par[N], de[N], mn[N][21];
vector<pair<int, int>>g[N];
bool f = 0;
// sol  => parents, deep, dist
// lp[v] = min dist for shop
// de[i] dist from E to int
// d[x] = deep
void sol(int v, int p = 0){
    par[v] = p;
    d[v] = d[p] + 1;
    for(auto i : g[v]){
        if(p != i.F && v != i.F){
            de[i.F] = de[v] + i.S;
            sol(i.F, v);
        }
    }
    for(auto i : g[v]){
        if(i.F != p)lp[v] = min(lp[v], lp[i.F] + i.S);
    }
}
int lca(int x, int y){
    if(d[x] <= d[y])swap(x, y);
    FORR(i, 17, 0, 1)if(d[y] <= d[up[x][i]])x = up[x][i];
    if(x == y)return y;
    FORR(i, 17, 0, 1)if(up[x][i] != up[y][i])x = up[x][i], y = up[y][i];
    return up[x][0];
}
int jump(int y, int x, int sum = 0, int ans = 0){
    ans = lp[y];
    FORR(i, 17, 0, 1){
        if( x >> i & 1 ){
            int ko = y;
            ans = min(ans, mn[y][i] + sum), y = up[y][i];
            sum += de[ko] - de[y];
        }
    }
    return ans;
}
void solve(){
    nikita
    int kokain;
    cin >> n >> m >> kokain >> cnt;
    FOR(i, 1, n-1, 1){
        cin >> a[i] >> b[i] >> r;
        x = a[i], y = b[i];
        g[x].pb({y, r}), g[y].pb({x, r});
    }
    FOR(i, 1, n, 1)lp[i] = 1e18;
    FOR(i, 1, m, 1)cin >> c[i], lp[c[i]] = 0;
    sol(cnt);
    lp[0] = 1e18, de[0] = 1e18;
    FOR(i, 1, n, 1)up[i][0] = par[i], mn[i][0] = min(lp[i], lp[par[i]] + de[i] - de[par[i]]);
    FOR(i, 1, 17, 1){
        FOR(j, 1, n, 1){
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
    while(n==1)ans++;
    FOR(i, 1, 17, 1){
        FOR(j, 1, n, 1){
            int dist = de[j] - de[up[j][i-1]];
            mn[j][i] = min(mn[j][i-1], mn[up[j][i-1]][i-1] + dist);
        }
    }
    FOR(i, 1, kokain, 1){
        cin >> x >> y;
        if(a[x] == lca(a[x], y) && b[x] == lca(b[x], y)){
            if(d[b[x]] > d[a[x]] && lp[b[x]] >= 1e18 || d[a[x]] < d[b[x]] && lp[a[x]] >= 1e18)cout << "oo\n";
            else{
            if(d[b[x]] > d[a[x]])swap(a[x], b[x]);
            int kok = jump(y, d[y] - d[a[x]]);
            if(kok>=1e11)cout << "oo\n";
            else cout<<kok<<'\n';
            }
            continue;
        }
        cout << "escaped"<<'\n';
    }
}
signed main()  
{  
    nikita  
    tt = 1;  
    if(!tt)cin >> tt;  
    FOR(i, 1, tt, 1){  
    solve();  
    }  
}

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