結果

問題 No.2915 辺更新価値最大化
ユーザー KudeKude
提出日時 2024-10-04 22:46:13
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 5,332 bytes
コンパイル時間 3,448 ms
コンパイル使用メモリ 300,260 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 22:46:18
合計ジャッジ時間 4,532 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 7 ms
5,248 KB
testcase_10 AC 7 ms
5,248 KB
testcase_11 AC 8 ms
5,248 KB
testcase_12 AC 7 ms
5,248 KB
testcase_13 AC 22 ms
5,248 KB
testcase_14 AC 23 ms
5,248 KB
testcase_15 AC 27 ms
5,248 KB
testcase_16 AC 30 ms
5,248 KB
testcase_17 AC 17 ms
5,248 KB
testcase_18 AC 17 ms
5,248 KB
testcase_19 AC 17 ms
5,248 KB
testcase_20 AC 17 ms
5,248 KB
testcase_21 AC 11 ms
5,248 KB
testcase_22 AC 3 ms
5,248 KB
testcase_23 AC 13 ms
5,248 KB
testcase_24 AC 9 ms
5,248 KB
testcase_25 AC 28 ms
5,248 KB
testcase_26 AC 11 ms
5,248 KB
testcase_27 AC 23 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

constexpr long long INF = 1002003004005006007;

// if dist[u] = INF, u is unreachable
// if dist[u] = -INF, u is inside a reachable negative cycle, or reachable from such a cycle

template<class T>
std::vector<long long> Bellman_Ford(const std::vector<std::vector<std::pair<int,T>>>& to, int s=0) {
    const int n = to.size();
    // make a permutation
    std::vector<int> p(n), p_inv(n);
    std::iota(p.begin(), p.end(), 0);
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    std::shuffle(p.begin(), p.end(), rng);
    for(int i = 0; i < n; i++) p_inv[p[i]] = i;

    // divide edges into two sets
    int ecnt[2] = {};
    for(int u = 0; u < n; u++) for(auto [v, _]: to[u]) {
        ecnt[p[u] > p[v]]++;
    }
    std::vector<std::pair<int, int>> vs[2]; // (vertex, id_e_right)
    std::vector<std::pair<int, T>> es[2];
    for(int k = 0; k < 2; k++) vs[k].reserve(n), es[k].reserve(ecnt[k]);
    int idx0 = 0, idx1 = ecnt[1];
    for(int pu = 0; pu < n; pu++) {
        int u = p_inv[pu];
        int idx0_old = idx0, idx1_old = idx1;
        for(auto [v, c]: to[u]) {
            if (pu <= p[v]) es[0].emplace_back(v, c), idx0++;
            else es[1].emplace_back(v, c), idx1--;
        }
        if (idx0 != idx0_old) vs[0].emplace_back(u, idx0);
        if (idx1 != idx1_old) vs[1].emplace_back(u, idx1_old);
    }
    std::reverse(vs[1].begin(), vs[1].end());
    std::reverse(es[1].begin(), es[1].end());

    std::vector<char> updated[2]; updated[0].resize(n), updated[1].resize(n);
    std::vector<long long> dist(n, INF);
    dist[s] = 0;
    updated[0][s] = updated[1][s] = true;
    const int max_iter = (n + 1) / 2; // forwards by at least two for each iteration, except for the first one; max_len = n - 1 <= 2(max_iter - 1) + 1
    for(int it = max_iter + 1; it > 0; it--) {
        bool any_updated = false;
        for(int k = 0; k < 2; k++) {
            int idx = 0;
            for(auto [u, r]: vs[k]) {
                if (!updated[k][u]) {
                    idx = r;
                    continue;
                }
                updated[k][u] = false;
                long long d = dist[u];
                for(; idx < r; idx++) {
                    auto [v, c] = es[k][idx];
                    long long nd = d + c;
                    if (nd < dist[v]) dist[v] = nd, updated[0][v] = updated[1][v] = any_updated = true;
                }
            }
        }
        if (!any_updated) return dist;
    }
    // contains negative cycle
    std::vector<char> is_inf(n, false);
    std::vector<int> todo;
    for(auto [u, r]: vs[0]) if (updated[0][u]) {
        is_inf[u] = true;
        dist[u] = -INF;
        todo.push_back(u);
    }
    while(!todo.empty()) {
        int u = todo.back(); todo.pop_back();
        for(auto [v, c]: to[u]) if (!is_inf[v]) {
            is_inf[v] = true;
            dist[v] = -INF;
            todo.push_back(v);
        }
    }
    return dist;
}

constexpr int IINF = 1001001001;
// constexpr long long INF = 1002003004005006007;
vector<int> dijkstra(const auto& to, int s = 0) {
  struct QueElem {
    int v;
    int d;
    bool operator<(const QueElem& a) const { return d > a.d; }
    QueElem(int v, int d) : v(v), d(d) {}
  };
  priority_queue<QueElem> q;
  vector<int> dist(to.size(), IINF);
  dist[s] = 0;
  q.emplace(s, 0);
  while (!q.empty()) {
    auto [u, d] = q.top(); q.pop();
    if (d > dist[u]) continue;
    for (auto [v, dv] : to[u]) {
      int nd = d + dv;
      if (nd < dist[v]) {
        dist[v] = nd;
        q.emplace(v, nd);
      }
    }
  }
  return dist;
}


} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<P>> to(n);
  struct E {
    int u, v, w;
  };
  vector<E> es(m);
  for (auto& [u, v, w] : es) {
    cin >> u >> v >> w;
    w *= -1;
    u--, v--;
    to[u].emplace_back(v, w);
  }
  auto pot = Bellman_Ford(to);
  assert(*min_element(all(pot)) != -INF);
  rep(u, n) for (auto& [v, w] : to[u]) {
    if (pot[u] == INF || pot[v] == INF) continue;
    w -= pot[v] - pot[u];
    assert(w >= 0);
  }
  for (auto& [u, v, w] : es) if (pot[u] != INF && pot[v] != INF) w -= pot[v] - pot[u];
  vector<char> used(m, true);
  rep(_, q) {
    int j;
    cin >> j;
    j--;
    auto [u, v, w] = es[j];
    if (used[j]) {
      used[j] = false;
      to[u].erase(ranges::find(to[u], P(v, w)));
    } else {
      used[j] = true;
      to[u].emplace_back(P(v, w));
    }
    int ans = dijkstra(to)[n - 1];
    if (ans == IINF) cout << "NaN\n";
    else cout << -(ans + pot[n - 1] - pot[0]) << '\n';
  }
}
0