oj.uz

답안 #204348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204348 2020-02-25T13:20:52 Z quocnguyen1012 Valley (BOI19_valley) C++14
100 / 100
 283 ms 41208 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 = 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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 9 ms 2936 KB Output is correct
3 Correct 9 ms 2936 KB Output is correct
4 Correct 9 ms 2936 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 9 ms 2936 KB Output is correct
3 Correct 9 ms 2936 KB Output is correct
4 Correct 9 ms 2936 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 8 ms 3192 KB Output is correct
7 Correct 7 ms 3064 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 7 ms 3064 KB Output is correct
10 Correct 7 ms 3064 KB Output is correct
11 Correct 7 ms 3064 KB Output is correct
12 Correct 7 ms 3064 KB Output is correct
13 Correct 7 ms 3064 KB Output is correct
14 Correct 7 ms 3064 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 34332 KB Output is correct
2 Correct 223 ms 37756 KB Output is correct
3 Correct 238 ms 37752 KB Output is correct
4 Correct 264 ms 39292 KB Output is correct
5 Correct 237 ms 39416 KB Output is correct
6 Correct 283 ms 40952 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 9 ms 2936 KB Output is correct
3 Correct 9 ms 2936 KB Output is correct
4 Correct 9 ms 2936 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 8 ms 3192 KB Output is correct
7 Correct 7 ms 3064 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 7 ms 3064 KB Output is correct
10 Correct 7 ms 3064 KB Output is correct
11 Correct 7 ms 3064 KB Output is correct
12 Correct 7 ms 3064 KB Output is correct
13 Correct 7 ms 3064 KB Output is correct
14 Correct 7 ms 3064 KB Output is correct
15 Correct 208 ms 34332 KB Output is correct
16 Correct 223 ms 37756 KB Output is correct
17 Correct 238 ms 37752 KB Output is correct
18 Correct 264 ms 39292 KB Output is correct
19 Correct 237 ms 39416 KB Output is correct
20 Correct 283 ms 40952 KB Output is correct
21 Correct 198 ms 37496 KB Output is correct
22 Correct 209 ms 37092 KB Output is correct
23 Correct 220 ms 37240 KB Output is correct
24 Correct 241 ms 38776 KB Output is correct
25 Correct 260 ms 41208 KB Output is correct
26 Correct 189 ms 37624 KB Output is correct
27 Correct 202 ms 37240 KB Output is correct
28 Correct 225 ms 37244 KB Output is correct
29 Correct 248 ms 38520 KB Output is correct
30 Correct 269 ms 39800 KB Output is correct
31 Correct 215 ms 37704 KB Output is correct
32 Correct 207 ms 37372 KB Output is correct
33 Correct 218 ms 37500 KB Output is correct
34 Correct 262 ms 38776 KB Output is correct
35 Correct 254 ms 41208 KB Output is correct
36 Correct 227 ms 38776 KB Output is correct