Submission #1275482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275482		TVSown	Valley (BOI19_valley)	C++17	36 / 100	3092 ms	9296 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define szz(s) int(s.size())
#define all(s) s.begin(), s.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n, s, q, E, TIME;
long long d[N], w[N], spe[N];
vector<pi> e[N];

void dfs(int u, int p, int i){
//    cout << u << " " << d[u] << "\n";
    for(auto [v, id] : e[u]){
        if(v == p || id == i) continue;
//        cout << u << " " << v << " " << id << "\n";
        d[v] = d[u] + w[id];
        dfs(v, u, i);
    }
}

void solve(){
    cin >> n >> s >> q >> E;
    FOR(i, 1, n - 1){
        int u, v; cin >> u >> v >> w[i];
        e[u].pb({v, i});
        e[v].pb({u, i});
    }
    FOR(i, 1, s){
        cin >> spe[i];
    }


    FOR(id, 1, q){
        int i, R; cin >> i >> R;
        FOR(u, 1, n) d[u] = -1;
        d[R] = 0;
        dfs(R, 0, i);
        if(d[E] != -1) cout << "escaped\n";
        else{
            long long res = 1e15;
            FOR(i, 1, s){
                if(d[spe[i]] == -1) continue;
                res = min(res, d[spe[i]]);
            }
            if(res == 1e15) cout << "oo\n";
            else cout << res << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
}

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