Submission #204348

#	Time	Username	Problem	Language	Result	Execution time	Memory
204348		quocnguyen1012	Valley (BOI19_valley)	C++14	100 / 100	283 ms	41208 KiB

valley

#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 = rmq[V[idx]][0] + dist[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]);
        x = par[x][k];
      }
    }
    if (res >= llinf) cout << "oo\n";
    else cout << res << '\n';
  }
}

Compilation message (stderr)

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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41