結果

問題 No.654 Air E869120
ユーザー shkiiii_shkiiii_
提出日時 2024-03-30 02:37:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 4,212 bytes
コンパイル時間 2,579 ms
コンパイル使用メモリ 224,036 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-09-30 17:24:57
合計ジャッジ時間 3,927 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 7 ms
5,248 KB
testcase_11 AC 6 ms
5,248 KB
testcase_12 AC 6 ms
5,248 KB
testcase_13 AC 7 ms
5,248 KB
testcase_14 AC 6 ms
5,248 KB
testcase_15 AC 6 ms
5,248 KB
testcase_16 AC 9 ms
5,248 KB
testcase_17 AC 11 ms
5,248 KB
testcase_18 AC 9 ms
5,248 KB
testcase_19 AC 9 ms
5,248 KB
testcase_20 AC 4 ms
5,248 KB
testcase_21 AC 5 ms
5,248 KB
testcase_22 AC 3 ms
5,248 KB
testcase_23 AC 3 ms
5,248 KB
testcase_24 AC 4 ms
5,248 KB
testcase_25 AC 3 ms
5,248 KB
testcase_26 AC 3 ms
5,248 KB
testcase_27 AC 3 ms
5,248 KB
testcase_28 AC 3 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 3 ms
5,248 KB
testcase_34 AC 3 ms
5,248 KB
testcase_35 AC 1 ms
5,248 KB
testcase_36 AC 1 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
// #include<atcoder/all>
// #include<boost/multiprecision/cpp_int.hpp>

using namespace std;
// using namespace atcoder;
// using bint = boost::multiprecision::cpp_int;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define sz(c) ((ll)(c).size())
#define LB(A,x) (int)(lower_bound(A.begin(),A.end(),x)-A.begin())
// #define MOD 1000000007
#define MOD 998244353
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<typename T>ostream&operator<<(ostream&os,vector<T>&v){for(int i = 0;i < v.size();i++)os<<v[i]<<(i+1!=v.size()?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}


// https://ei1333.github.io/luzhiled/snippets/graph/dinic.html
template<typename flow_t>
struct Dinic{
  /*
    復元をするときはfromの頂点から出る辺からのcapを出力．
    is_e == trueの時その辺は元のグラフにあった"本当の"辺．
    "本当の"辺eについてfr -> toにv[e.to][e.ref].capだけフローが流れている．
    二部マッチングの復元の場合，仮想の始点（終点）から（へ）の辺に注意．
  */
  struct edge{
    int to;
    flow_t cap;
    int ref;//逆辺の番号
    bool is_e;//本物の辺かどうか
    int idx;//入力で与えられる辺としてのindex
  };
  vector<vector<edge>> v;
  vector<int> mn_cost,iter;
  const flow_t inf;
  Dinic(int n):inf(numeric_limits<flow_t>::max()),v(n){}
  void add_edge(int fr,int to,flow_t cap,int idx = -1){
    v[fr].emplace_back((edge){to,cap,(int)v[to].size(),true,idx});
    v[to].emplace_back((edge){fr,0,(int)v[fr].size()-1,false,idx});
  }
  bool bfs(int s,int t){
    mn_cost.assign(v.size(),-1);
    queue<int> que;
    mn_cost[s] = 0;
    que.push(s);
    while(!que.empty() && mn_cost[t] == -1){
      int ov = que.front();que.pop();
      for(auto &e : v[ov]){
        if(e.cap > 0 && mn_cost[e.to] == -1){
          mn_cost[e.to] = mn_cost[ov] + 1;
          que.push(e.to);
        }
      }
    }
    return mn_cost[t] != -1;
  }
  flow_t dfs(int ov,const int t,flow_t flow){
    if(ov == t)return flow;
    for(int &i = iter[ov];i < v[ov].size();i++){
      edge &e = v[ov][i];
      if(e.cap > 0 && mn_cost[ov] < mn_cost[e.to]){
        flow_t d = dfs(e.to,t,min(flow,e.cap));
        if(d > 0){
          e.cap -= d;
          v[e.to][e.ref].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  // O(m n^2)(n:頂点数 m:辺数)
  flow_t max_flow(int s,int t){
    flow_t flow = 0;
    while(bfs(s,t)){
      iter.assign(v.size(),0);
      flow_t f = 0;
      while((f = dfs(s,t,inf)) > 0)flow += f;
    }
    return flow;
  }
  void output(){
    for(int i = 0;i < v.size();i++){
      for(auto &e : v[i]) {
        if(!e.is_e) continue;
        auto &rev_e = v[e.to][e.ref];
        cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << "\n";
      }
    }
  }
};

int main(){
  
  ios_base::sync_with_stdio(0), cin.tie(0);
  ll n,m,D;
  cin >> n >> m >> D;
  const ll inf = 1ll << 50;
  vvi v(m,vi(5));
  rep(i,m){
    cin >> v[i];
    rep(j,2)v[i][j]--;
  }
  vvi air(n);
  air[0].emplace_back(0);
  air[n-1].emplace_back(1ll << 32);
  rep(i,m){
    air[v[i][0]].emplace_back(v[i][2]);
    air[v[i][1]].emplace_back(v[i][3]+D);
  }
  vi rui(n+1);
  rep(i,n){
    sort(ALL(air[i]));
    air[i].erase(unique(ALL(air[i])),air[i].end());
    rui[i+1] = rui[i] + sz(air[i]);
  }
  Dinic<ll> dn(rui.back());
  rep(i,m){
    dn.add_edge(rui[v[i][0]]+LB(air[v[i][0]],v[i][2]),rui[v[i][1]]+LB(air[v[i][1]],v[i][3]+D),v[i][4]);
  }
  rep(i,n){
    rep(j,sz(air[i])-1){
      dn.add_edge(rui[i]+j,rui[i]+j+1,inf);
    }
  }
  cout << dn.max_flow(0,rui.back()-1) << "\n";

  

  return 0;
}
0