제출 #1307946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307946		shisp1	Valley (BOI19_valley)	C++20	59 / 100	3097 ms	51412 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9+7;
const ll inf = 1e18;
const int N = 2e5+5;
int n,s,q,e, a[N], U[N], V[N], W[N], up[N][20], timer = 0, tin[N], tout[N];
vector<int>g2[N];
set<pair<int,int>>g[N];
void dfs(int v, int p) {
    tin[v] = ++timer;
    up[v][0] = p;
    for(int i = 1;i<20;i++) {
        up[v][i] = up[up[v][i-1]][i-1];
    }
    for(auto to:g2[v]) {
        if(to == p) continue;
        dfs(to,v);
    }
    tout[v] = timer;
}
bool check(int a, int b) {
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}
void solve() {
    cin >> n >> s >> q >> e;
    vector<pair<int,int>>edjes;
    for(int i = 1;i<n;i++) {
        cin >> U[i] >> V[i] >> W[i];
        g2[U[i]].pb(V[i]);
        g2[V[i]].pb(U[i]);
        g[U[i]].insert({V[i],W[i]});
        g[V[i]].insert({U[i],W[i]});
    }
    for(int i = 1;i<=s;i++) {
        cin >> a[i];
    }
    if(s == n) {
        dfs(e,e);
        while(q--) {
            int i, r;
            cin >> i >> r;
            int u = U[i], v=V[i];
            int c = (up[v][0] == u ? v : u);
            if(check(c,r) == check(c,e)) {
                cout << "escaped\n";
            } else {
                cout << "0\n";
            }
        }
    } else {
        while(q--){
            int i,r;
            cin >> i >> r;
            int uu = U[i], vv =V[i], ww = W[i];
            g[uu].erase({vv,ww});
            g[vv].erase({uu,ww});
            vector<int>dist(n+1,inf);
            dist[r] = 0;
            set<pair<int,int>>st;
            st.insert({0,r});
            while(st.size()) {
                auto [dv,ver] = *st.begin();
                st.erase(st.begin());
                for(auto [to,weight]:g[ver]) {
                    if(dist[to]>dist[ver]+weight) {
                        st.erase({dist[to],to});
                        dist[to] = dist[ver]+weight;
                        st.insert({dist[to],to});
                    }
                }
            }
            if(dist[e]!=inf) {
                cout << "escaped\n";
            }
            else {
                int mn = 1e18;
                for(int i = 1;i<=s;i++) {
                    if(dist[a[i]]!=inf) {
                        mn = min(mn,dist[a[i]]);
                    }
                }
                if(mn == 1e18) {
                    cout << "oo\n";
                } else {
                    cout << mn << "\n";
                }
            }
            g[uu].insert({vv,ww});
            g[vv].insert({uu,ww});
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--) {
        solve();
    }





    return 0;
}

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