Submission #1246833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246833		Kacper_Ziemecki	Valley (BOI19_valley)	C++20	59 / 100	3095 ms	22824 KiB

valley

#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();
}

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