oj.uz

Submission #862978

# Submission time Handle Problem Language Result Execution time Memory
862978 2023-10-19T12:17:37 Z Erfan1386Y Valley (BOI19_valley) C++14
59 / 100
 3000 ms 18896 KB 
#include <bits/stdc++.h>
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);
#define what(x) cerr << #x << " is " << x << endl;
#define kill(x) {cout << x << '\n'; continue;}
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ll long long
#define F first
#define S second
const ll inf = 1e14, mod = 1e9 + 7, delta = 1e8, SQ = 800; //998244353

using namespace std;

const ll N = 1e5 + 10, LG = 20;

#define piii array<int, 3>
int cnt, st[N], ft[N];
vector<piii> adj[N];
vector<int> maghaze, t;
pll par[N], d[N], dd[N], edges[N];
bitset<N> mark;
ll dis[N];

void dfs (int v, int p, int e) {
  t.pb(v);
  st[v] = cnt++;
  par[v] = pii(p, e);
  for (auto u: adj[v])
    if (u[0] - p) dfs(u[0], v, u[2]);
  ft[v] = cnt;
}

void dfs (int v, int e) {
  mark[v] = true;
  for (auto u: adj[v])
    if (u[2] != e && !mark[u[0]])
      dfs(u[0], e);
}

bool cmp (piii a, piii b){
  return a[1] < b[1];
}

int32_t main() {
  fast_io;
  int n, s, q, e;
  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].pb({v, w, i});
    adj[v].pb({u, w, i});
    edges[i] = pii(u, v);
  }
  for (int i = 1; i <= s; i++) {
    int v;
    cin >> v;
    maghaze.pb(v);
  }
  if (s == n) {
    dfs(1, -1, -1);
    for (int j = 1; j <= q; j++) {
      int ii, r;
      cin >> ii >> r;
      int u = edges[ii].F, v = edges[ii].S;
      if (v == par[u].F) swap(u, v);
      bool b = (st[e] >= st[v] && st[e] < ft[v]), bb = (st[r] >= st[v] && st[r] < ft[v]);
      if (b && bb) cout << "escaped\n";
      else if (b || bb) cout << "0\n";
      else cout << "escaped\n";
    }
  }
  else {
    while (q--) {
      int ii, r;
      cin >> ii >> r;
      mark.reset();
      dfs(r, ii);
      if (mark[e]) kill("escaped");
      mark.reset();
      priority_queue<pii, vector<pii>, greater<pii>> q;
      q.push(pii(0, r));
      memset(dis, 63, sizeof dis);
      dis[r] = 0;
      while (q.size()) {
        int v = q.top().S;
        q.pop();
        if (mark[v]) continue;
        mark[v] = true;
        for (auto u: adj[v]) {
          if (u[2] != ii && dis[u[0]] > dis[v] + u[1]) {
            dis[u[0]] = dis[v] + u[1];
            q.push(pii(dis[u[0]], u[0]));
          }
        }
      }
      ll mn = inf;
      for (auto u: maghaze) mn = min(mn, dis[u]);
      if (mn == inf) cout << "oo\n";
      else cout << mn << '\n';
    }
  }
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5824 KB Output is correct
2 Correct 45 ms 5824 KB Output is correct
3 Correct 42 ms 5724 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5824 KB Output is correct
2 Correct 45 ms 5824 KB Output is correct
3 Correct 42 ms 5724 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 10 ms 5724 KB Output is correct
6 Correct 13 ms 5820 KB Output is correct
7 Correct 14 ms 5724 KB Output is correct
8 Correct 11 ms 5824 KB Output is correct
9 Correct 12 ms 5724 KB Output is correct
10 Correct 34 ms 5720 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 26 ms 5820 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16372 KB Output is correct
2 Correct 80 ms 15956 KB Output is correct
3 Correct 63 ms 15800 KB Output is correct
4 Correct 84 ms 17020 KB Output is correct
5 Correct 62 ms 16972 KB Output is correct
6 Correct 63 ms 18896 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5824 KB Output is correct
2 Correct 45 ms 5824 KB Output is correct
3 Correct 42 ms 5724 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 10 ms 5724 KB Output is correct
6 Correct 13 ms 5820 KB Output is correct
7 Correct 14 ms 5724 KB Output is correct
8 Correct 11 ms 5824 KB Output is correct
9 Correct 12 ms 5724 KB Output is correct
10 Correct 34 ms 5720 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 26 ms 5820 KB Output is correct
15 Correct 86 ms 16372 KB Output is correct
16 Correct 80 ms 15956 KB Output is correct
17 Correct 63 ms 15800 KB Output is correct
18 Correct 84 ms 17020 KB Output is correct
19 Correct 62 ms 16972 KB Output is correct
20 Correct 63 ms 18896 KB Output is correct
21 Execution timed out 3074 ms 14932 KB Time limit exceeded
22 Halted 0 ms 0 KB -