Submission #644893

#	Time	Username	Problem	Language	Result	Execution time	Memory
644893		mychecksedad	Valley (BOI19_valley)	C++17	36 / 100	3078 ms	32512 KiB

valley

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

struct Edge{
    int next;
    ll e;
    int idx;
};

int n, s, q, E, forb;
vector<Edge> g[N];
vector<array<int, 3>> edges;
vector<bool> edg(N, 1), c(N);
bool ok;
void dfs(int v, int p, vector<ll>&dist){
    if(v == E) ok = 1;
    for(Edge e: g[v]){
        int u = e.next;
        if(e.idx == forb) continue;
        if(u != p){
            dist[u] = dist[v] + e.e;
            dfs(u, v, dist);
        }
    }
}
void solve(){
    cin >> n >> s >> q >> E;
    for(int i = 0; i < n - 1; ++i){
        int u, v, e; cin >> u >> v >> e;
        Edge ee = {u, e, i + 1};
        g[v].pb(ee);
        ee.next = v;
        g[u].pb(ee);
        edges.pb({u, v, e});
    }
    for(int i = 1; i <= s; ++i){
        int x; cin >> x;
        c[x] = 1;
    }

    for(;q--;){
        int i, v; cin >> i >> v;
        vector<ll> dist(n+2, ll(1e15));
        ok = 0;
        dist[v] = 0;
        forb = i;
        dfs(v, 0, dist);
        ll mn = 1e15;
        for(int i = 1; i <= n; ++i){
            if(c[i] && dist[i] < 1e15){
                mn = min(mn, dist[i]);
            }
        }
        if(ok) cout << "escaped";
        else if(mn == 1e15) cout << "oo";
        else cout << mn;
        cout << '\n';
    }

        
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:80:16: warning: unused variable 'aa' [-Wunused-variable]
   80 |     int T = 1, aa;
      |                ^~

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