Submission #175685

#	Time	Username	Problem	Language	Result	Execution time	Memory
175685		AlexLuchianov	Valley (BOI19_valley)	C++14	100 / 100	598 ms	42912 KiB

valley

#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 (stderr)

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