Submission #1327354

#TimeUsernameProblemLanguageResultExecution timeMemory
1327354mtilordValley (BOI19_valley)C++20
0 / 100
3093 ms7540 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

vector<array<int, 3>> mas[100001];
bool shop[100001];
int e;
int dfs(int v, int p, int in, int pgar)
{
    if(v==e)
        return -1;
    int g;
    if(shop[v]==1)
        g=pgar;
    else
        g=INT_MAX;

    for(auto [vr, gar, id]:mas[v])
    {
        if(id==in || vr==p)
            continue;
        else
            g=min(g, dfs(vr, v, in, pgar+gar));
    }
    return g;

}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, s, q;
    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        mas[a].pb({b, w, i});
        mas[b].pb({a, w, i});
    }
    for(int i=0; i<s; i++)
    {
        int a;
        cin >> a;
        shop[a]=1;
    }
    for(int i=0; i<q; i++)
    {
        int in, r;
        cin >> in >> r;
        int atb=dfs(r, r, in, 0);
        if(atb==-1)
            cout << "escaped" << endl;
        else if(atb==INT_MAX)
            cout << "oo" << endl;
        else
            cout << atb << endl;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...