제출 #1313484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313484		ghammazhassan	Valley (BOI19_valley)	C++20	23 / 100	382 ms	50648 KiB

valley

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e14;
const int LOG=17;
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
vector<pair<int,int>>a[N];
map<pair<int,int>,int>in;
map<int,pair<int,int>>it;
int sh[N];
int dp[N];
int di[N];
int vi[N];
int av[N];
int p[LOG][N];
void makest(){
    for (int j=1;j<LOG;j++){
        for (int i=1;i<=n;i++){
            p[j][i]=p[j-1][p[j-1][i]];
        }
    }
}
int bl(int x,int d){
    int k=LOG-1;
    while (k>=0){
        if ((1<<k)<=d){
            d-=1<<k;
            x=p[k][x];
        }
        k--;
    }
    return x;
}
void dfs(int x,int y){
    for (auto [i,w]:a[x]){
        if (i==y)continue;
        dfs(i,x);
        dp[x]=min(dp[x],dp[i]+w);
    }
}
void dfs1(int x,int y){
    for (auto [i,w]:a[x]){
        if (i==y)continue;
        dp[i]=min(dp[i],dp[x]+w);
        dfs1(i,x);
    }
}
void solve(){
    int s,q,e;
    cin >> n >> s >> q >> e;
    for (int i=0;i<n-1;i++){
        cin >> x >> y >> w;
        a[x].push_back({y,w});
        a[y].push_back({x,w});
        in[{x,y}]=i;
        in[{y,x}]=i;
        it[i]={x,y};
    }
    for (int i=1;i<=n;i++){
        dp[i]=inf;
    }
    for (int i=0;i<s;i++){
        cin >> x;
        sh[x]=1;
        dp[x]=0;
    }
    queue<int>o;
    o.push(e);
    vi[e]=1;
    di[e]=1;

    while (o.size()){
        int h=o.front();
        o.pop();
        for (auto [i,w]:a[h]){
            if (vi[i])continue;
            vi[i]=1;
            di[i]=di[h]+1;
            p[0][i]=h;
            o.push(i);
        }
    }
    makest();
    dfs(e,0);
    for (int i=1;i<=n;i++){
        if (dp[i]<inf){
            av[i]=1;
        }
        vi[i]=0;
    }
    priority_queue<pair<int,int>>oq;
    for (int i=1;i<=n;i++){
        if (sh[i]){
            oq.push({0,i});
        }
    }
    while (oq.size()){
        int h=oq.top().se;
        oq.pop();
        if (vi[h])continue;
        vi[h]=1;
        for (auto [i,w]:a[h]){
            if (vi[i])continue;
            dp[i]=min(dp[i],dp[h]+w);
            oq.push({-dp[i],i});
        }
    }
    for (int i=0;i<q;i++){
        int j,k;
        cin >> k >> j;
        k--;
        x=it[k].fi,y=it[k].se;
        if (di[x]>di[y])swap(x,y);
        if (di[y]>di[j]){
            cout << "escaped" << endl;
            continue;
        }
        if (bl(j,di[j]-di[y])!=y or bl(j,di[j]-di[x])!=x){
            cout << "escaped" << endl;
            continue;
        }
        if (av[y]){
            cout << dp[j] << endl;
        }
        else{
            cout << "oo" << endl;
        }
    }
}
signed main()    
{   
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r" ,stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
}

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