oj.uz

Submission #204347

# Submission time Handle Problem Language Result Execution time Memory
204347 2020-02-25T13:17:07 Z quocnguyen1012 Valley (BOI19_valley) C++14
0 / 100
 202 ms 34680 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
const ll llinf = 1e17;

int U[maxn], V[maxn], W[maxn];
vector<int> adj[maxn];
int N, Q, S, E;
bool mark[maxn];
int tin[maxn], tout[maxn];
ll dist[maxn], rmq[maxn][20], D[maxn];
int par[maxn][20], depth[maxn];

void precalc(int u, int p = -1)
{
  static int nTime = 0;
  tin[u] = ++nTime;
  for (int i = 1; (1 << i) <= N; ++i)
    par[u][i] = par[par[u][i - 1]][i - 1];
  D[u] = llinf;
  if (mark[u]) D[u] = dist[u];
  for (int i : adj[u]){
    int v = U[i] + V[i] - u;
    int w = W[i];
    if (v == p) continue;
    dist[v] = dist[u] + w;
    depth[v] = depth[u] + 1;
    par[v][0] = u;
    precalc(v, u);
    D[u] = min(D[u], D[v]);
  }
  tout[u] = nTime;
  if (D[u] != llinf) rmq[u][0] = D[u] - 2 * dist[u];
  else rmq[u][0] = llinf;
}

bool in(int u, int v)
{
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> S >> Q >> E;
  for (int i = 1; i < N; ++i){
    cin >> U[i] >> V[i] >> W[i];
    adj[U[i]].pb(i); adj[V[i]].pb(i);
  }
  for (int i = 1; i <= S; ++i){
    int x; cin >> x;
    mark[x] = true;
  }
  depth[E] = 1;
  precalc(E);
  for (int i = 1; i < N; ++i){
    if (tin[V[i]] < tin[U[i]]) swap(U[i], V[i]);
  }
  for (int j = 1; (1 << j) <= N; ++j){
    for (int i = 1; i <= N; ++i){
      rmq[i][j] = min(rmq[i][j - 1], rmq[par[i][j - 1]][j - 1]);
    }
  }
  while (Q--){
    int idx, x; cin >> idx >> x;
    if (!in(V[idx], x)){
      cout << "escaped\n";
      continue;
    }
    ll now = dist[x], res = dist[x] + D[x];
    //cerr << V[idx] << '\n';
    for (int k = 19; k >= 0; --k){
      if (depth[par[x][k]] >= depth[V[idx]]){
        res = min(res, now + rmq[x][k + 1]);
        x = par[x][k];
      }
    }
    if (res >= llinf) cout << "oo\n";
    else cout << res << '\n';
  }
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 34680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2812 KB Output isn't correct
2 Halted 0 ms 0 KB -