Submission #1104737

#TimeUsernameProblemLanguageResultExecution timeMemory
1104737khanhgngValley (BOI19_valley)C++17
36 / 100
3077 ms9404 KiB
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define bit(x, i) ((x >> (i)) & 1)
#define SZ(x) ((int)(x.size()))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define task "LANDSLIDE"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }

const int MAXn = 1e5 + 5;
const int MOD = 1e9 + 7;
const int BASE = 3137;
const int BL = 320;
const ll oo = (long long)(1e18);

int n,S,Q,H,I,R;
ll ans=MOD;
bool lt[MAXn],issafe=0,isok=0;
struct edge{
    int v;
    ll w;
    int id;
    edge(int vv=0,ll ww=0,int idd=0):v(vv),w(ww),id(idd){};
};
vector<edge>adj[MAXn];

void dfs(int u,int par,ll sumw){
    if(u==H){issafe=1;return;}
    if(lt[u]){isok=1;ans=min(ans,sumw);}
    for(edge x:adj[u]){
        if(x.v==par)continue;
        if(x.id==I)continue;
        dfs(x.v,u,sumw+x.w);
    }
}

void solve() {
    cin>>n>>S>>Q>>H;
    FOR(i,1,n-1){
        int u,v;ll w;cin>>u>>v>>w;
        adj[u].pb(edge(v,w,i));
        adj[v].pb(edge(u,w,i));
    }
    FOR(i,1,S){int C;cin>>C;lt[C]=1;}
    while(Q--){
        issafe=0;isok=0;ans=oo;
        cin>>I>>R;
        dfs(R,0,0LL);
        if(issafe)cout<<"escaped\n";
        else{
            if(isok){cout<<ans<<'\n';}
            else cout<<"oo\n";
        }
    }
}

int32_t main() {
    if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
    ios::sync_with_stdio(0); cin.tie(0);
    int ntest = 1; //cin >> ntest;
    while (ntest--) solve();
    cerr << "\n\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:67:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:67:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...