oj.uz

답안 #175685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
175685 2020-01-07T09:47:16 Z AlexLuchianov Valley (BOI19_valley) C++14
100 / 100
 598 ms 42912 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;
//ifstream in ("input.txt");

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
ll const inf = 1000000000000000000LL;

struct Edge{
  int to;
  int cost;
};
vector<Edge> g[1 + nmax];
int edge[1 + nmax][2], special[1 + nmax], pos[1 + nmax], posend[1 + nmax], ptr = 0;
ll level[1 + nmax], dp[1 + nmax];
vector<pair<int,int>> query[1 + nmax];

void dfs(int node, int parent){
  if(special[node] == 1)
    dp[node] = 0;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h].to;
    if(to == parent) {
      g[node].erase(g[node].begin() + h);
      break;
    }
  }

  pos[node] = ptr + 1;
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    level[e.to] = level[node] + e.cost;
    dfs(e.to, node);
    dp[node] = MIN(dp[node], dp[e.to] + e.cost);
  }
  posend[node] = ++ptr;
}

class SegmentTree{
private:
vector<ll> aint;
public:
SegmentTree(int n){
    aint.resize(4 * n);
  }
  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
    aint[node] = inf;
  }
  void update(int node, int from, int to, int x, int y, ll val){
    if(from == x && to == y)
      aint[node] = MIN(aint[node], val);
    else {
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(mid, y), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
    }
  }
  ll query(int node, int from, int to, int x){
    if(from < to){
      int mid = (from + to) / 2;
      ll result;
      if(x <= mid)
        result = query(node * 2, from, mid, x);
      else
        result = query(node * 2 + 1, mid + 1, to, x);
      return MIN(result, aint[node]);
    } else
      return aint[node];
  }
};
int n;

ll sol[1 + nmax];

void solve(int node, SegmentTree &aint){
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    solve(e.to, aint);
  }
  aint.update(1, 1, n, pos[node], posend[node], dp[node] - level[node]);

  for(int h = 0; h < query[node].size(); h++){
    int target = query[node][h].first, id = query[node][h].second;
    if(pos[node] <= posend[target] && posend[target] <= posend[node]){
      sol[id] = level[target] + aint.query(1, 1, n, posend[target]);
    } else
      sol[id] = -1;
  }
}

int main()
{
  int s, q, root;
  cin >> n >> s >> q >> root;
  for(int i = 1;i < n; i++){
    int x, y, cost;
    cin >> x >> y >> cost;
    g[x].push_back({y, cost});
    g[y].push_back({x, cost});
    edge[i][0] = x;
    edge[i][1] = y;
  }
  for(int i = 1;i <= n; i++)
    dp[i] = inf;
  for(int i = 1;i <= s; i++){
    int x;
    cin >> x;
    special[x]++;
  }
  dfs(root, 0);
  SegmentTree aint(n);
  aint.build(1, 1, n);

  for(int i = 1;i <= q; i++){
    int id, node;
    cin >> id >> node;
    int queried = edge[id][0];
    if(level[edge[id][0]] < level[edge[id][1]])
      queried = edge[id][1];
    query[queried].push_back({node, i});
  }
  solve(root, aint);

  for(int i = 1; i <= q; i++) {
    if(sol[i] == -1)
      cout << "escaped\n";
    else if(sol[i] < inf)
      cout << sol[i] << '\n';
    else
      cout << "oo\n";
  }
  return 0;
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
valley.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void solve(int, SegmentTree&)':
valley.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
valley.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < query[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5368 KB Output is correct
2 Correct 14 ms 5496 KB Output is correct
3 Correct 14 ms 5368 KB Output is correct
4 Correct 14 ms 5436 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5368 KB Output is correct
2 Correct 14 ms 5496 KB Output is correct
3 Correct 14 ms 5368 KB Output is correct
4 Correct 14 ms 5436 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 9 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 9 ms 5208 KB Output is correct
11 Correct 9 ms 5232 KB Output is correct
12 Correct 9 ms 5240 KB Output is correct
13 Correct 10 ms 5372 KB Output is correct
14 Correct 9 ms 5368 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 465 ms 19292 KB Output is correct
2 Correct 535 ms 22764 KB Output is correct
3 Correct 496 ms 22776 KB Output is correct
4 Correct 516 ms 31228 KB Output is correct
5 Correct 496 ms 30200 KB Output is correct
6 Correct 598 ms 40312 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5368 KB Output is correct
2 Correct 14 ms 5496 KB Output is correct
3 Correct 14 ms 5368 KB Output is correct
4 Correct 14 ms 5436 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 9 ms 5240 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 9 ms 5208 KB Output is correct
11 Correct 9 ms 5232 KB Output is correct
12 Correct 9 ms 5240 KB Output is correct
13 Correct 10 ms 5372 KB Output is correct
14 Correct 9 ms 5368 KB Output is correct
15 Correct 465 ms 19292 KB Output is correct
16 Correct 535 ms 22764 KB Output is correct
17 Correct 496 ms 22776 KB Output is correct
18 Correct 516 ms 31228 KB Output is correct
19 Correct 496 ms 30200 KB Output is correct
20 Correct 598 ms 40312 KB Output is correct
21 Correct 417 ms 22192 KB Output is correct
22 Correct 433 ms 21760 KB Output is correct
23 Correct 447 ms 21828 KB Output is correct
24 Correct 471 ms 31540 KB Output is correct
25 Correct 474 ms 42872 KB Output is correct
26 Correct 422 ms 22520 KB Output is correct
27 Correct 437 ms 21960 KB Output is correct
28 Correct 450 ms 22284 KB Output is correct
29 Correct 467 ms 28076 KB Output is correct
30 Correct 493 ms 33620 KB Output is correct
31 Correct 423 ms 22648 KB Output is correct
32 Correct 435 ms 22364 KB Output is correct
33 Correct 456 ms 22628 KB Output is correct
34 Correct 487 ms 30584 KB Output is correct
35 Correct 478 ms 42912 KB Output is correct
36 Correct 452 ms 31096 KB Output is correct