Submission #733383

#	Time	Username	Problem	Language	Result	Execution time	Memory
733383		tch1cherin	Robot (JOI21_ho_t4)	C++17	0 / 100	595 ms	153456 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct segment_tree {
  int lx, rx;
  long long min_value, push;
  int unused; 
  segment_tree* left = nullptr;
  segment_tree* right = nullptr;

  segment_tree(int _lx, int _rx) : lx(_lx), rx(_rx) {
    min_value = push = LLONG_MAX;
    unused = 0;
  }

  void apply(long long v) {
    min_value = min(min_value, v);
    push = min(push, v);
  }

  void propagate() {
    if (push == LLONG_MAX) {
      return;
    }
    if (left) {
      left->apply(push); 
    }
    if (right) {
      right->apply(push);
    }
    push = LLONG_MAX; 
  }

  void pull() {
    min_value = push = LLONG_MAX;
    unused = 0;
    if (left) {
      if (left->unused > 0) {
        min_value = min(min_value, left->min_value);
        unused += left->unused;
      }
    }
    if (right) {
      if (right->unused > 0) {
        min_value = min(min_value, right->min_value);
        unused += right->unused;
      }
    }
  }

  void Left() { left = (left ? left : new segment_tree(lx, (lx + rx) / 2)); }

  void Right() { right = (right ? right : new segment_tree((lx + rx) / 2, rx)); }

  void update(int l, int r, long long v) {
    if (lx >= l && rx <= r) {
      apply(v);
    } else {
      propagate();
      int mid = (lx + rx) / 2;
      if (l < mid) {
        Left();
        left->update(l, r, v);
      }
      if (r > mid) {
        Right();
        right->update(l, r, v);
      }
      pull();
    }
  }

  void modify(int i, long long v, bool is_unused) {
    if (rx - lx == 1) {
      if (!is_unused) {
        unused = 0;
        min_value = push = LLONG_MAX;
      } else {
        unused = 1;
        min_value = push = v;
      }
    } else {
      propagate();
      int mid = (lx + rx) / 2;
      if (i < mid) {
        Left();
        left->modify(i, v, is_unused);
      } else {
        Right();
        right->modify(i, v, is_unused);
      }
      pull();
    }
  }

  pair<long long, int> get_min() {
    if (unused == 0) {
      return {LLONG_MAX, -1};
    } else if (!left && !right) {
      return {min_value, lx};
    } else {
      propagate();
      bool left_good = left && left->min_value == min_value && left->unused > 0;
      bool right_good = right && right->min_value == min_value && right->unused > 0;
      if (left_good) {
        return left->get_min();
      } else if (right_good) {
        return right->get_min();
      } else {
        if (left && (left->min_value != min_value || left->unused == 0)) {
          return {min_value, (lx + rx) / 2}; 
        } else {
          return {min_value, lx}; 
        }
      }
    }
  }
};

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<map<int, long long>> sum(n), dist(n);
  vector<map<int, vector<pair<int, int>>>> g(n);
  vector<segment_tree> st(n, segment_tree(0, 2 << __lg(m)));
  for (int i = 0; i < m; i++) {
    int a, b, c, p;
    cin >> a >> b >> c >> p;
    a--, b--;
    g[a][c].emplace_back(b, p);
    g[b][c].emplace_back(a, p);
    sum[a][c] += p;
    sum[b][c] += p;
  }
  min_heap<tuple<long long, int, int>> q;
  for (int i = 1; i < n; i++) {
    for (auto [color, value] : sum[i]) {
      st[i].modify(color, LLONG_MAX, true);
    }
  }
  for (auto [color, value] : sum[0]) {
    q.emplace(0, 0, color);
    dist[0][color] = 0;
  }
  set<pair<int, int>> used;
  long long ans = LLONG_MAX;
  while (!q.empty()) {
    auto [d, u, nxt] = q.top();
    q.pop();
    if (used.count({u, nxt})) {
      continue;
    }
    used.emplace(u, nxt);
    st[u].modify(nxt, dist[u][nxt], false);
    auto [MinValue, Pos] = st[u].get_min();
    if (Pos != -1) {
      dist[u][Pos] = MinValue; 
      q.emplace(MinValue, u, Pos);
    }
    auto S = sum[u][nxt], D = dist[u][nxt];
    for (auto [v, p] : g[u][nxt]) {
      if (v == n - 1) {
        ans = min({ans, D + p, D + S - p});
      }
      st[v].update(0, 2 << __lg(m), D + p);
      if (nxt > 0) {
        st[v].update(0, nxt, D + S - p);
      }
      if (nxt + 1 < (2 << __lg(m))) {
        st[v].update(nxt + 1, 2 << __lg(m), D + S - p);
      }
      auto [min_value, pos] = st[v].get_min();
      if (pos != -1) {
        if (dist[v].count(pos)) {
          dist[v][pos] = min(dist[v][pos], min_value);
        } else {
          dist[v][pos] = min_value;
        }
        q.emplace(min_value, v, pos);
      } 
    }
  }
  cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42