Submission #1327406

#TimeUsernameProblemLanguageResultExecution timeMemory
1327406madtValley (BOI19_valley)C++20
23 / 100
228 ms15044 KiB
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e5+5;
const ll INF = 1e18+8;
vector<array<ll, 2>> edges[100'002];
vector<array<ll, 2>> eg;
bool shop[100'002];

int tin[N], tout[N];
int tim=0;
ll e;

ll dfs(ll u, ll block, ll p=0, ll dist=0){
    tim++;
    tin[u]=tim;

    ll tta;
    if(shop[u])
        tta=dist;
    else tta=INF;

    for(auto x : edges[u]){
        if(x[0]!=p){
            tta=min(tta, dfs(x[0], block, u, dist+x[1]));
        }
    }
    tout[u]=tim;
    return tta;
}

bool isinside(int a, int b){
    //vai a ir ieks b

    if(tin[b]<=tin[a] && tout[b]>=tout[a])
        return 1;
    else
        return 0;
}

int main()
{
    ll n, s, q; cin>>n>>s>>q>>e;
    eg.push_back({0, 0});
    for(ll i=1; i<n; i++){
        ll a, b, w; cin>>a>>b>>w;
        edges[a].push_back({b, w});
        edges[b].push_back({a, w});
        eg.push_back({a, b});
    }

    for(ll i=0; i<s; i++){
        ll s; cin>>s;
        shop[s]=1;
    }

    dfs(e, -1);

//    for(int i=0; i<n; i++){
//        cout<<tin[i]<<' '<<tout[i]<<endl;
//    }

    for(ll i=0; i<q; i++){
        ll u, block; cin>>block>>u;
        // pienem a ir 1 un b ir 1

        int a=eg[block][0], b=eg[block][1];
        int atb=-1;
//        cout<<"SIe: "<<a<<' '<<isinside(u, a)<<' '<<b<<' '<<isinside(u, b)<<endl;

        if(isinside(u, a) && isinside(u, b))
            atb=0;

        if(atb==-1)
            cout<<"escaped"<<endl;
        else if(atb==INF)
            cout<<"oo"<<endl;
        else
            cout<<atb<<endl;
    }

    return 0;
}
/*

5 5 3 1
1 2 3
1 3 2
3 4 1
3 5 2
1
2
3
4
5
2 2
2 5
4 5

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...