제출 #1317199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317199		vaishakhv	Valley (BOI19_valley)	C++20	36 / 100	3093 ms	13052 KiB

valley

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll cap = 1e5+1;
vector<pair<ll,ll>> adj[cap];

void dijkstra(){

}
int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, s, q, e;
    cin >> n >> s >> q >> e;

    vector<tuple<ll,ll,ll>> edges;
    for (ll i{}; i < n-1; i++){
        ll a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        edges.push_back({a,b,w});
    }   

    vector<ll> shops;

    for (ll i{}; i < s; i++){
        ll c; cin >> c;
        shops.push_back(c);
    }

    for (ll i{}; i < q; i++){
        ll I, r; cin >> I >> r;
        ll a, b, w; tie(a, b, w) = edges[I-1];
        erase(adj[a], make_pair(b, w));
        erase(adj[b], make_pair(a, w));

        priority_queue<pair<ll,ll>> pq;
        vector<bool> visited(n+1, false);
        vector<ll> dist(n+1, 1e18);

        dist[r] = 0;
        pq.push({0, r});

        while (!pq.empty()){
            auto t = pq.top(); pq.pop();
            ll d = -t.first;
            ll v = t.second;

            if (visited[v]) continue;
            visited[v] = true;

            for (auto pr : adj[v]){
                ll u = pr.first;
                ll wt = pr.second;

                if (dist[u] > d + wt){
                    dist[u] = d + wt;
                    pq.push({-dist[u], u});
                }
            }
        }

        if (dist[e] == 1e18) {
            ll ans = 1e18;
            for (ll v : shops) {
                ans = min(ans, dist[v]);
            }

            if (ans == 1e18) {
                cout << "oo\n";
            } else {
                cout << ans << "\n";
            }
        } else {
            cout << "escaped\n";
        }


        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
}

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