Submission #123017

#	Time	Username	Problem	Language	Result	Execution time	Memory
123017		model_code	Valley (BOI19_valley)	C++17	36 / 100	3032 ms	9132 KiB

valley

/* should pass subtasks 1, 2, 3 */
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

pair<int, int> make_edge (int u, int v) {
  return make_pair(min(u, v), max(u, v));
}

const int maxn = 100005;
const ll inf = 1LL << 60;

vector<pair<int, ll>> adj [maxn];
bool is_store [maxn];

void query_dfs (int vertex, int parent, int root, pair<int, int> forbidden, ll cur_dist, ll &ans) {
  if (vertex == root) {
    ans = -1;
  }
  if (is_store[vertex]) {
    ans = min(cur_dist, ans);
  }
  
  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent && make_edge(vertex, nxt.first) != forbidden) {
      query_dfs(nxt.first, vertex, root, forbidden, cur_dist + nxt.second, ans);
    }
  }
}

ll query (int vertex, int root, pair<int, int> forbidden) {
  ll ans = inf;
  query_dfs(vertex, -1, root, forbidden, 0, ans);
  return ans;
}

int main () {
  int vertexc, storec, queryc, root;
  cin >> vertexc >> storec >> queryc >> root;

  vector<pair<int, int>> edges;
  for (int i = 0; i < vertexc - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
    edges.push_back(make_edge(u, v));
  }

  for (int i = 0; i < storec; i++) {
    int x;
    cin >> x;
    is_store[x] = true;
  }

  for (int i = 0; i < queryc; i++) {
    int forb_id, cur_vertex;
    cin >> forb_id >> cur_vertex;

    ll ans = query(cur_vertex, root, edges[forb_id - 1]);
    if (ans == -1) {
      cout << "escaped" << '\n';
    } else if (ans == inf) {
      cout << "oo" << '\n';
    } else {
      cout << ans << '\n';
    }
  }
}

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