Submission #733454

#	Time	Username	Problem	Language	Result	Execution time	Memory
733454		tch1cherin	Robot (JOI21_ho_t4)	C++17	100 / 100	1642 ms	131920 KiB

Main

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

struct container {
  int a = -1;
  long long x = LLONG_MAX, y = LLONG_MAX;
  vector<int> S;

  container() {}

  container(vector<int> s) : S(s) {}

  void update_all(long long v) {
    x = min(x, v);
    y = min(y, v);
  }

  void update_exclusive(int i, long long v) {
    if (v < x) {
      if (a != i) {
        y = x;
        a = i;
      }
      x = v;
    } else {
      if (a != i) {
        y = min(y, v);
      }
    }
  }

  pair<long long, int> get_min() {
    if (S.empty()) {
      return {LLONG_MAX, -1};
    } else if (S.size() == 1) {
      return {(S.back() == a ? y : x), S.back()};
    } else {
      return {x, (S.back() == a ? end(S)[-2] : S.back())};
    }
  }

  void pop() {
    assert(!S.empty());
    if (S.back() == a) {
      if (S.size() == 1) {
        S.pop_back();
        x = y = LLONG_MAX;
      } else {
        S.pop_back();
        S.pop_back();
        S.push_back(a); 
      }
    } else {
      S.pop_back();
    }
  }
};

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<tuple<int, int, int>>>> g(n);
  vector<container> C(n);
  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, c);
    g[b][c].emplace_back(a, p, c);
    sum[a][c] += p;
    sum[b][c] += p;
  }
  min_heap<tuple<long long, int, int, bool>> q;
  for (int i = 0; i < n; i++) {
    vector<int> d;
    for (auto [k, v] : sum[i]) {
      d.push_back(k);
      dist[i][k] = LLONG_MAX;
    }
    d.push_back(m + 1 + i);
    dist[i][m + 1 + i] = LLONG_MAX;
    vector<tuple<int, int, int>> gc;
    for (auto [k, cc] : g[i]) {
      for (auto [v, p, col] : cc) {
        gc.emplace_back(v, p, col);
      }
    }
    g[i][m + 1 + i] = gc;
    sort(d.begin(), d.end());
    d.resize(unique(d.begin(), d.end()) - d.begin());
    C[i] = container(d);
    if (i == 0) {
      for (int v : d) {
        q.emplace(0, 0, v, true);
        dist[0][v] = 0;
      }
    }
  }
  long long ans = LLONG_MAX;
  set<pair<int, int>> used, popped;
  while (!q.empty()) {
    auto [d, u, nxt, del] = q.top();
    q.pop();
    if (used.count({u, nxt})) {
      continue;
    }
    used.insert({u, nxt});
    if (C[u].get_min().second == nxt) {
      C[u].pop();
    }
    while (!C[u].S.empty()) {
      auto [min_value, pos] = C[u].get_min();  
      if (!dist[u].count(pos) || dist[u][pos] > min_value) {
        dist[u][pos] = min_value;
        q.emplace(min_value, u, pos, true);
        break;
      }
      if (used.count({u, pos})) {
        C[u].pop();
      } else {
        break;
      }
    }
    long long D = dist[u][nxt], S = sum[u][nxt];
    for (auto [v, p, col] : g[u][nxt]) {
      if (v == n - 1) {
        ans = min({ans, (nxt == m + 1 + u ? D + p : LLONG_MAX), (nxt == m + 1 + u ? LLONG_MAX : D + S - p)});
      }
      if (nxt != m + 1 + u) {
        C[v].update_exclusive(nxt, D + S - p);
      } else {
        C[v].update_all(D + p);
        if (!dist[v].count(col) || dist[v][col] > D) {
          dist[v][col] = D;
          q.emplace(dist[v][col], v, col, false); 
        }
      } 
      while (!C[v].S.empty()) { 
        auto [min_value, pos] = C[v].get_min();
        if (!dist[v].count(pos) || dist[v][pos] > min_value) {
          dist[v][pos] = min_value;
          q.emplace(min_value, v, pos, true);
        }
        if (used.count({v, pos})) {
          C[v].pop();
        } else {
          break;
        }
      }
    }
  }
  cout << (ans == LLONG_MAX ? -1 : ans) << "\n";
}

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

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