結果

問題 No.654 Air E869120
コンテスト
ユーザー yuppe19 😺
提出日時 2019-03-16 19:37:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 2,877 bytes
コンパイル時間 1,516 ms
コンパイル使用メモリ 109,792 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 22:38:38
合計ジャッジ時間 3,161 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
using i64 = int64_t;

struct edge { size_t to; i64 avail; int rev; };
constexpr i64 inf = 987'654'321'987'654'321LL;

size_t n;
vector<vector<edge>> G;
vector<int> ptr;
vector<bool> used;

void add_edge(size_t u, size_t v, i64 c) {
//  fprintf(stderr, "%lu -> %lu: %d\n", u, v, c);
  G[u].push_back(edge{v, c, ptr[v]++});
  G[v].push_back(edge{u, 0, ptr[u]++});
}

i64 dfs(size_t v, size_t t, i64 flow) {
  if(v == t) { return flow; }
  used[v] = true;
  for(edge &e : G[v]) {
    edge &x = G[e.to][e.rev];
    if(!used[e.to] && e.avail) {
      i64 res = dfs(e.to, t, min(flow, e.avail));
      if(res) {
        e.avail -= res;
        x.avail += res;
        return res;
      }
    }
  }
  return 0;
}

i64 max_flow(size_t s, size_t t) {
  i64 res = 0;
  for(;;) {
    used.assign(n, false);
    i64 flow = dfs(s, t, inf);
    if(flow == 0) { return res; }
    res += flow;
  }
}

template <class T>
size_t index(const vector<T> &a, T key) {
  return lower_bound(a.begin(), a.end(), key) - a.begin();
}

int main(void) {
  int N, M, d; scanf("%d%d%d", &N, &M, &d);
  vector<tuple<int, int, bool>> nodes;
  vector<tuple<int, int, int, int, int>> logs;
  for(int i=0; i<M; ++i) {
    int u, v, t0, t1, w; scanf("%d%d%d%d%d", &u, &v, &t0, &t1, &w);
    logs.emplace_back(u, v, t0, t1, w);
    nodes.emplace_back(u, t0, true);
    nodes.emplace_back(v, t1, false);
  }

  sort(begin(nodes), end(nodes)); nodes.erase(unique(begin(nodes), end(nodes)), end(nodes));

  vector<tuple<int, int, bool>> deps, arrs;
  deps.emplace_back(-1, -1, true);
  for(auto tup : nodes) {
    int v, time_; bool is_dep; tie(v, time_, is_dep) = tup;
    if(is_dep) {
      deps.emplace_back(v, time_, is_dep);
    } else {
      arrs.emplace_back(v, time_, is_dep);
    }
  }
  deps.emplace_back(inf, inf, true);

  ::n = nodes.size() + 2;
  size_t src = ::n - 2, dst = ::n - 1;
  G.assign(n, vector<edge>());
  ptr.assign(n, 0);

  // フライト
  for(auto tup : logs) {
    int u, v, t0, t1, w; tie(u, v, t0, t1, w) = tup;
    size_t p0 = index(nodes, make_tuple(u, t0, true)),
           p1 = index(nodes, make_tuple(v, t1, false));
    add_edge(p0, p1, w);
  }

  // 始点
  for(auto tup : deps) {
    if(get<0>(tup) == 1) {
      size_t p0 = index(nodes, tup);
      add_edge(src, p0, inf);
    }
  }

  // 終点
  for(auto tup : arrs) {
    int v, time_; bool flag; tie(v, time_, flag) = tup;
    size_t p0 = index(nodes, tup);
    if(v == N) {
      add_edge(p0, dst, inf);
    }
    size_t lo = index(deps, make_tuple(v,   time_+d, true)),
           hi = index(deps, make_tuple(v+1, 0,       true));
    for(size_t p=lo; p<hi; ++p) {
      size_t p1 = index(nodes, deps[p]);
      add_edge(p0, p1, inf);
    }
  }

  i64 maxi = max_flow(src, dst);
  printf("%ld\n", maxi);

  return 0;
}
0