제출 #1327317

#제출 시각아이디문제언어결과실행 시간메모리
1327317mtilordValley (BOI19_valley)C++20
0 / 100
138 ms11964 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<pii> mas[100001];
int main()
{

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

    int n, s, q, e;
    cin >> n >> s >> q >> e;
    set<int> shop;
    for(int i=0; i<n-1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        mas[a].pb({w, b});
        mas[b].pb({w, a});
    }
    for(int i=0; i<s; i++)
    {
        int a;
        cin >> a;
        shop.insert(a);
    }
    for(int i=0; i<q; i++)
    {
        int in, r;
        cin >> in >> r;
        if((in>r && in>=e) || (in<r && in<e))
        {
            cout << "escaped" << endl;
        }
        else
        {
            int atb=INT_MAX;
            queue<pii> rinda;
            bool biju[n+1]={};
            rinda.push({0, r});
            biju[r]=1;
            while(!rinda.empty())
            {
                int v=rinda.front().se, w=rinda.front().fi;
                rinda.pop();
                biju[v]=1;
                if(shop.count(v)!=0)
                {
                    atb=w;
                    break;
                }
                for(auto x:mas[v])
                {
                    if(biju[x.se]==0 && !(v>x.se && in==x.se))

                        rinda.push(x);
                }
            }
            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...