Submission #1317190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317190		discontinuous	Valley (BOI19_valley)	C++20	36 / 100	3097 ms	83524 KiB

valley

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

#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int INF = 1e15;
const int N = 1e6;

int n, m, k, a, b, c, d, h, l, r, q, u, v, x, y;
int s, e;

vector<int> arr(N);
vector<set<int>> adj(N);
vector<bool> vis(N);
map<pair<int, int>, int> weight;
set<int> shops;
bool found = 0;

void dfs(int node, int d) {
    if(found) return;
    vis[node] = 1;
    // cout << node << " ";
    if(node==e) {
        // cout << node << " ";
        found = true;
        return;
    }

    if(shops.find(node) != shops.end()) {
        c = min(c, d);
        // cout << c << " ";
    }
    for(auto j : adj[node]) {
        if(!vis[j]) {
            dfs(j, d+weight[{node, j}]);
        }
    }
}

void solve() {
    cin >> n >> s >> q >> e;

    vector<pair<int, int>> edges(n+1);
    for(int i = 1; i<n; i++) {
        cin >> a >> b >> c;
        adj[a].insert(b);
        adj[b].insert(a);

        weight[{a, b}] = c;
        weight[{b, a}] = c;
        
        edges[i] = {a, b};
    }  


    for(int i = 0; i<s; i++) {
        cin >> a;
        shops.insert(a);
    }

    while(q--) {
        cin >> l >> r;
        adj[edges[l].first].erase(edges[l].second);
        adj[edges[l].second].erase(edges[l].first);
        c = INF;
        found = 0;
        dfs(r, 0);

        if(found) cout << "escaped";
        else if(c == INF) {
            cout << "oo";
        }
        else {
            cout << c;
        }
        cout << "\n";

        adj[edges[l].first].insert(edges[l].second);
        adj[edges[l].second].insert(edges[l].first);
        for(int i = 1; i<=n; i++) vis[i] = 0;
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int tc = 1;
    // cin >> tc;

    while(tc--) {
        solve();
        cout << "\n";
    }

    return 0;
}

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