Submission #644907

#	Time	Username	Problem	Language	Result	Execution time	Memory
644907		mychecksedad	Valley (BOI19_valley)	C++17	36 / 100	99 ms	33052 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, tin[N], tout[N], timer = 0, dep[N];
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 pre(int v, int p){
    tin[v]++;
    dep[v] = dep[p] + 1;
    for(Edge u: g[v]){
        if(u.next != p) pre(u.next, v);
    }
    tout[v]++;
}
bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
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;
    }
    dep[E] = 0;
    pre(E, 0);
    if(s != n || n <= 1000){
        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';
        }
    }else{
        for(;q--;){
            int i, v; cin >> i >> v;
            int node1 = edges[i - 1][0];
            int node2 = edges[i - 1][1];
            if(dep[node2] < dep[node1]) swap(node1, node2);
            if(is_ancestor(node1, v)) cout << 0;
            else cout << "escaped";
            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:103:16: warning: unused variable 'aa' [-Wunused-variable]
  103 |     int T = 1, aa;
      |                ^~

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