oj.uz

Submission #536425

# Submission time Handle Problem Language Result Execution time Memory
536425 2022-03-13T09:47:43 Z cig32 Valley (BOI19_valley) C++17
36 / 100
 3000 ms 20904 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 120717661;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}

vector<pair<int, int> > adj[MAXN];

int oh[MAXN];
int shop[MAXN];
int x, y; // edge removed
vector<pair<int, int> > edges;
int dep[MAXN];
int tin[MAXN], tout[MAXN];
int par[MAXN];
int wow = 0;
void dfs(int node, int prv, int cur) {
  oh[node] = 1e18;
  dep[node] = cur;
  tin[node] = ++wow;
  par[node] = prv;
  for(auto x: adj[node]) {
    if(x.first != prv) {
      dfs(x.first, node, cur + x.second);
      oh[node] = min(oh[node], oh[x.first]);
    }
  }
  tout[node] = ++wow;
  if(shop[node]) oh[node] = cur;
}
void solve(int tc) {
  int n, s, q, e;
  cin >> n >> s >> q >> e;
  for(int i=1; i<n; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    edges.push_back({a, b});
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }
  for(int i=0; i<s; i++) {
    int c; cin >> c;
    shop[c] = 1;
  }
  dfs(e, -1, 0);
  while(q--) {
    int i, r;
    cin >> i >> r;
    if(n == 1) {
      cout << "escaped\n";
      continue;
    }
    i--;
    x = edges[i].first, y = edges[i].second;
    if(tin[x] > tin[y]) swap(x, y);
    if(!(tin[y] <= tin[r] && tout[r] <= tout[y])) {
      cout << "escaped\n";
    }
    else {
      int og = r;
      int ans = 1e18;
      while(1) {
        ans = min(ans, dep[og] + oh[r] - 2 * dep[r]);
        if(r != y) r = par[r];
        else break;
      }
      cout << (ans >= 1e14 ? "oo" : to_string(ans)) << "\n";
    }
  }

}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 5 ms 5156 KB Output is correct
3 Correct 6 ms 5076 KB Output is correct
4 Correct 6 ms 5076 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 5 ms 5156 KB Output is correct
3 Correct 6 ms 5076 KB Output is correct
4 Correct 6 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 17048 KB Output is correct
2 Correct 113 ms 16944 KB Output is correct
3 Correct 138 ms 17148 KB Output is correct
4 Correct 1338 ms 19136 KB Output is correct
5 Correct 2742 ms 19164 KB Output is correct
6 Execution timed out 3078 ms 20904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 5 ms 5156 KB Output is correct
3 Correct 6 ms 5076 KB Output is correct
4 Correct 6 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 6 ms 5204 KB Output is correct
15 Correct 103 ms 17048 KB Output is correct
16 Correct 113 ms 16944 KB Output is correct
17 Correct 138 ms 17148 KB Output is correct
18 Correct 1338 ms 19136 KB Output is correct
19 Correct 2742 ms 19164 KB Output is correct
20 Execution timed out 3078 ms 20904 KB Time limit exceeded
21 Halted 0 ms 0 KB -