제출 #1246833

#제출 시각아이디문제언어결과실행 시간메모리
1246833Kacper_ZiemeckiValley (BOI19_valley)C++20
59 / 100
3095 ms22824 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define pb push_back void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) ll timer = 0; ll in[100001],out[100001]; vector<pair<ll,ll>> adj[100001]; set<ll> shops; bool flag = false; void dfs(ll u, ll p){ in[u] = timer++; for(auto [v,w] : adj[u]){ if(v != p) dfs(v,u); } out[u] = timer++; } bool is_ancestor(ll up, ll low){ return (in[up] <= in[low] && out[up] >= out[low]); } ll bfs(ll u){ ll res = LLONG_MAX; bool vis[100001]; if(!flag) memset(vis, false, sizeof(vis)); queue<pair<ll,ll>> q; vis[u] = true; q.push({u,0}); while(!q.empty()){ pair<ll,ll> parent = q.front(); q.pop(); if(shops.count(parent.first)) res = min(res, parent.second); for(auto child : adj[parent.first]){ if(!vis[child.first]){ vis[child.first] = true; q.push({child.first, parent.second + child.second}); } } } return res; } void solve() { ll n,s,q,e,a,b; cin >> n >> s >> q >> e; if(n==s) flag = true; vector<vector<ll>> lista(n, vector<ll>(3, 0)); for(int i = 0; i < n-1; i++){ for(int j = 0; j < 3; j++) cin >> lista[i][j]; } for(auto el : lista){ adj[el[0]].pb({el[1], el[2]}); adj[el[1]].pb({el[0], el[2]}); } for(ll i = 0; i < s; i++){ cin >> a; shops.emplace(a); } dfs(e, e); // for(ll i = 0; i < n+1; i++) dbg(i, in[i], out[i]); for(int i = 0; i < q; i++){ cin >> a >> b; // dbg(lista[a-1][0], lista[a-1][1]); if(is_ancestor(lista[a-1][0],b) && is_ancestor(lista[a-1][1],b)){ adj[lista[a-1][0]].erase(find(adj[lista[a-1][0]].begin(), adj[lista[a-1][0]].end(), make_pair(lista[a-1][1], lista[a-1][2]))); adj[lista[a-1][1]].erase(find(adj[lista[a-1][1]].begin(), adj[lista[a-1][1]].end(), make_pair(lista[a-1][0], lista[a-1][2]))); // dbg(n); // for(ll k = 1; k <= n; k++){ // cout << k << " -> "; // for(ll j = 0; j < adj[k].size(); j++) cout << adj[k][j].first << " "; // cout << endl; // } ll res = bfs(b); // dbg(res); cout << (res == LLONG_MAX ? "oo" : to_string(res)) << endl; adj[lista[a-1][0]].pb({lista[a-1][1], lista[a-1][2]}); adj[lista[a-1][1]].pb({lista[a-1][0], lista[a-1][2]}); } else{ cout << "escaped\n"; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...