#347399 (C++14) No.654 Air E869120

提出ソース

結果

問題	No.654 Air E869120
ユーザー	syaro
提出日時	2019-05-17 23:45:39
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	70 ms / 2,000 ms
コード長	13,303 bytes
コンパイル時間	2,198 ms
コンパイル使用メモリ	139,160 KB
実行使用メモリ	66,816 KB
最終ジャッジ日時	2024-09-17 06:03:57
合計ジャッジ時間	4,202 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	18 ms 6,944 KB
testcase_11	AC	17 ms 6,944 KB
testcase_12	AC	14 ms 6,944 KB
testcase_13	AC	17 ms 6,940 KB
testcase_14	AC	16 ms 6,940 KB
testcase_15	AC	15 ms 6,944 KB
testcase_16	AC	68 ms 66,816 KB
testcase_17	AC	70 ms 66,688 KB
testcase_18	AC	70 ms 66,688 KB
testcase_19	AC	69 ms 66,688 KB
testcase_20	AC	50 ms 66,688 KB
testcase_21	AC	51 ms 66,688 KB
testcase_22	AC	46 ms 66,816 KB
testcase_23	AC	47 ms 66,688 KB
testcase_24	AC	50 ms 66,688 KB
testcase_25	AC	46 ms 66,688 KB
testcase_26	AC	47 ms 66,816 KB
testcase_27	AC	45 ms 66,688 KB
testcase_28	AC	47 ms 66,560 KB
testcase_29	AC	46 ms 66,688 KB
testcase_30	AC	46 ms 66,560 KB
testcase_31	AC	46 ms 66,560 KB
testcase_32	AC	45 ms 66,688 KB
testcase_33	AC	46 ms 66,560 KB
testcase_34	AC	46 ms 66,688 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	1 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*? begin "base.hpp" */
#ifndef __clang__
#pragma GCC optimize ("O3")
#endif
void solve( /* この関数に問題ごとの処理を書く */
#ifdef GCJ_CASE
 long long case_id
#endif
);

#if defined(EBUG) && !defined(ONLINE_JUDGE)
 #define debug true
#else
 #define NDEBUG 
 #define debug false
#endif
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<type_traits>
#include<vector>
#ifdef __cpp_lib_execution
  #include<execution>
#endif
#include<cassert>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>

using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define int LL 
#define CS const
#define CX constexpr
#define IL inline
#define RT return
#define TL template
#define TN typename
#define lambda [&]
#define times(n,i) uptil(0,n,i)
#define rtimes(n,i) downto((n)-1,0,i)
#define upto(f,t,i) for(int rabT##i=(t),i=(f);i<=rabT##i;i++)
#define uptil(f,t,i) for(int rabT##i=(t),i=(f);i< rabT##i;i++)
#define downto(f,t,i) for(int rabT##i=(t),i=(f);i>=rabT##i;i--)
#define downtil(f,t,i) for(int rabT##i=(t),i=(f);i> rabT##i;i--)
#define iter(v) begin(v),end(v)
#define citer(v) cbegin(v),cend(v)
#define riter(v) rbegin(v),rend(v)
#define criter(v) crbegin(v),crend(v)
#define IF(a,b,c) ((a)?(b):(c))
#define BINOP_ASGN(t,u,op) t operator op(CS u&o)CS{RT t(*this)op##=o;}
#if debug
 #define _GLIBCXX_DEBUG
 #define _LIBCPP_DEBUG 2
 #define _LIBCPP_DEBUG2 2
 #define ln <<endl
#else
 #define ln <<'\n'
#endif
#define tb <<'\t'
#define sp <<' '
 #define PARABLE 
/*? begin "mod.hpp" */
#ifdef MOD
 #if !defined(FORCE_MOD)&&MOD!=1000000007&&MOD!=1000000009&&MOD!=998244353
  #error unknown mod MOD and FORCE_MOD not defined.
 #endif
#else
 #define MOD 1000000007
#endif
/*? begin "power.hpp" */
using int128=__int128;
TL<TN T>T power(T x,int n){T rt(1);for(;n;n/=2){if(n%2)rt*=x;x*=x;}RT rt;}
int pow_mod(int x,int n,int m){int rt=1;for(;n;n/=2){if(n%2)rt=rt*x%m;x=x*x%m;}RT rt;}
int128 pow_mod_64(int128 x,int n,int m){int128 rt=1;for(;n;n/=2){if(n%2)rt=rt*x%m;x=x*x%m;}RT rt;}
/*? end "power.hpp" */
IL CX int modulo(int a,int m){RT(a%=m,a>=0?a:a+m);}
TL<ULL mod=MOD>class MInt{
  /*! https://ei1333.github.io/luzhiled/snippets/other/mod-int.html */
public:
  int val;
  CX MInt():val(0){}
  explicit CX MInt(int v):val(modulo(v,mod)){}
  MInt&operator+=(CS MInt&m){val+=m.val;if(val>=mod)val-=mod;RT*this;}
  MInt&operator-=(CS MInt&m){val-=m.val;if(val<0)val+=mod;RT*this;}
  MInt&operator*=(CS MInt&m){val=val*m.val%mod;RT*this;}
  MInt&operator/=(CS MInt&m){val=val*m.inv().val%mod;RT*this;}
  BINOP_ASGN(MInt,MInt,+) BINOP_ASGN(MInt,MInt,-) BINOP_ASGN(MInt,MInt,*) BINOP_ASGN(MInt,MInt,/)
  MInt operator-()CS{MInt m;m.val=val?mod-val:0;RT m;}
  bool operator==(CS MInt&m)CS{RT val==m.val;}
  bool operator!=(CS MInt&m)CS{RT val!=m.val;}
  //MInt pow(int n)CS{MInt x(*this),rt(1);while(n){if(n%2)rt*=x;x*=x;n/=2;}RT rt;}
  MInt pow(int n)CS{RT power(*this,n);}
  MInt inv()CS{int a=val,b=mod,x=1,y=0,t;while(b){t=a/b;swap(b,a-=t*b);swap(y,x-=t*y);}RT(MInt)x;}
  friend ostream&operator<<(ostream&o,CS MInt<mod>&m){RT o<<m.val;}
  friend istream&operator>>(istream&i,MInt<mod>&m){int v;i>>v;m=MInt<mod>(v);RT i;}
};
using mint=MInt<>;

constexpr mint operator"" _m(ULL n){RT mint(n);}
constexpr MInt<998244353>operator"" _m998244353(ULL n){RT MInt<998244353>(n);}
constexpr MInt<1000000007>operator"" _m1e9_7(ULL n){RT MInt<1000000007>(n);}
constexpr MInt<1000000009>operator"" _m1e9_9(ULL n){RT MInt<1000000009>(n);}

//#pragma rab:gsub \b(\d+)m\b mint(\1)
/*? end "mod.hpp" */
/*? begin "typedefs.hpp" */
struct unit{};

using int128=__int128;
using LD=long double;
TL<TN T>using vec=vector<T>;
TL<TN T>using vvec=vec<vec<T>>;
TL<TN T>using vvvec=vec<vvec<T>>;
TL<TN T>using vvvvec=vec<vvvec<T>>;

//#pragma rab typedefs.dynamic
using WI = vvec<int>; using VI = vec<int>; using VPII = vec<pair<int, int>>; 
/*? end "typedefs.hpp" */
/*? begin "alias.hpp" */
#define PB push_back
#define foldl accumulate
#define scanl partial_sum
/*? end "alias.hpp" */
/*? begin "util.hpp" */
TL<TN T>IL bool amax(T&v,CS T&a){RT v<a&&(v=a,true);}
TL<TN T>IL bool amin(T&v,CS T&a){RT v>a&&(v=a,true);}

#ifndef __cpp_lib_exchange_function
 #define exchange exchange_RAB
 TL<TN T,TN U=T>IL T exchange(T& t, U&& u){T x=move(t);t=forward<U>(u);RT x;}
#endif
#ifndef __cpp_lib_clamp
 #define clamp clamp_RAB
 TL<TN T>IL CX CS T&clamp(CS T&a,CS T&mn,CS T&mx){RT a<mn?mn:a>mx?mx:a;}
#endif

TL<TN T>IL int size_RAB(T t){RT t.size();}
#define size size_RAB

TL<TN V>IL void uniq_after_sort(V&v){v.erase(unique(iter(v)),v.end());}
TL<TN V>IL void sort_and_uniq(V&v){sort(iter(v));v.erase(unique(iter(v)),v.end());}
TL<TN V,TN K>IL auto leftmost_ge(CS V&v,CS K&k){RT v.lower_bound(k);}
TL<TN V,TN K>IL auto leftmost_gt(CS V&v,CS K&k){RT v.upper_bound(k);}

namespace rab{

TL<TN V,TN W>IL void append(V&v,CS W&w){copy(PARABLE citer(w),back_inserter(v));}

TL<TN V>IL auto flatten(CS V&xss,int reserve_size=0)->TN V::value_type{
  decltype(flatten(xss))ret;
  ret.reserve(reserve_size);
  for(CS auto&xs:xss)append(ret,xs);
  ret.shrink_to_fit();
  RT move(ret);
}

TL<TN I>IL bool is_in(I x,I l,I r){RT l<=x&&x<r;}

TL<TN T>IL T fetch(CS T&d,CS vec<T>&v,int i){RT 0<=i&&i<size(v)?v[i]:d;}
TL<TN T>IL T fetch(CS T&d,CS vvec<T>&v,int i,int j){
  RT 0<=i&&i<size(v)&&0<=j&&j<size(v[i])?v[i][j]:d;
}
// TL<TN T,TN U,TN...I>IL T fetch(CS T&d,CS vec<vec<U>>&v,int i,I...j){
// RT 0<=i&&i<size(v)?fetch(d,v[i],j...):d;
// }
TL<TN T>struct Compressed{int size;map<T,int>zip;vec<T>unzip;};
TL<TN T>IL Compressed<T>compressed(vec<T>v){
  sort_and_uniq(v);map<T,int>zip;times(size(v),i)zip[v[i]]=i;RT{size(v),zip,move(v)};
}
TL<TN T>struct CompressedSrc{int size;map<T,int>zip;vec<T>unzip;WI src;};
TL<TN T>IL CompressedSrc<T>compressed_src(CS vec<T>&v){
  auto c=compressed(v);VI src(c.size);times(size(v),i)src[c.zip[v[i]]].PB(i);RT{c.size,c.zip,c.unzip,src};
}

struct identity{TL<TN U>U operator()(U&&v)CS{RT v;}};
}
/*? end "util.hpp" */
/*? begin "debug.hpp" */
TL<class T>
IL istream&operator>>(istream&s,vec<T>&v){for(auto&&p:v)s>>p;RT s;}
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS pair<T,S>&p){RT s<<"("<<p.first<<","<<p.second<<")";}
TL<class T>
IL ostream&operator<<(ostream&,CS vec<T>&);
TL<class T,class S>
IL ostream&operator<<(ostream&,CS map<T,S>&);
#define DEFINE_ITER_OUTPUT(s,x,sep){int i=0;for(CS auto&x##0_elem:x){if(i++)s<<sep;s<<x##0_elem;}RT s;}
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<T>&v)DEFINE_ITER_OUTPUT(s,v,' ')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS map<T,S>&m)DEFINE_ITER_OUTPUT(s,m,' ')
TL<class T>
IL ostream&operator<<(ostream&s,CS vec<vec<T>>&w)DEFINE_ITER_OUTPUT(s,w,'\n')
TL<class T,class S>
IL ostream&operator<<(ostream&s,CS vec<map<T,S>>&v)DEFINE_ITER_OUTPUT(s,v,'\n')
/*? end "debug.hpp" */

signed main(){
 {if(debug)cerr<<"MOD: "<<(MOD)ln;}
 if(!debug)cin.tie(0),cerr.tie(0),ios::sync_with_stdio(0);
 cout<<fixed<<setprecision(20);
 cerr<<fixed<<setprecision(20);

 #ifdef GCJ_CASE
  int T;cin>>T;
  times(T,t){cout<<"Case #"<<t+1<<": ";solve(t);}
 #else
  solve();
 #endif

 return 0;
}
/*? end "base.hpp" */
/*? begin "graph.hpp" */
/*? begin "uf.hpp" */

template<class T = int, class Adder = plus<T>, class Inverser = negate<T>>
class UnionFind {
  /*
    ポテンシャル付きUnionFind (find: path compression, merge: union by size)

    FUNC:
      merge: 既にマージされていたならfalse, 今回マージ処理を行ったならtrueを返す.

    TIME:
      new, clear:           O(n).
      root, merge, is_same: 償却O(a(n)); ただしaはアッカーマン関数の逆関数.

    TMPL:
      T: ポテンシャルの型
      Adder: ポテンシャルの和演算 (群の演算)
      Inverser: ポテンシャルの逆元関数
      例: UnionFind<int, bit_xor<int>, identity<int>>
  */
  /*!
    http://noshi91.hatenablog.com/entry/2018/05/30/191943
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://qiita.com/drken/items/cce6fc5c579051e64fab
  */

  int n, *parents, *sizes;
  T *pot_diffs;
  bool to_delete;
  Adder adder;
  Inverser inverser;

public:
  explicit UnionFind(int n, bool to_delete = false):
    n(n), parents(new int[n]), sizes(new int[n]), pot_diffs(new T[n]), to_delete(to_delete)
  {
    clear();
  }

  void clear() {
    times(n, i) parents[i] = i; /* roots */
    fill(sizes, sizes + n, 1);
    fill(pot_diffs, pot_diffs + n, 0);
  }

  ~UnionFind(){if(to_delete){delete[]parents;delete[]sizes;delete[]pot_diffs;}}

  int size() { return n; }

  int root(int i) {
    int p = parents[i];
    if(p == i) return i; /* `i` is a root */
    int r = root(p); /* and pot_diffs[p] := diff from root */
    pot_diffs[i] += pot_diffs[p];
    parents[i] = r;
    return r;
  }

  bool is_same(int i,int j){RT root(i)==root(j);}
  bool is_all_same(){int r=root(0);uptil(1,n,i)if(root(i)!=r)RT 0;RT 1;}

  bool merge(int i, int j, T pdiff = 0) {
    i = root(i);
    j = root(j);
    if(i == j) return false; /* already merged */
    if(sizes[i] > sizes[j]) {
      swap(i, j);
      pdiff = inverser(pdiff);
    }
    /* now sizes[i] <= sizes[j] */
    parents[i] = j;
    sizes[j] += sizes[i];
    pot_diffs[i] = pdiff;
    return true;
  }

  T diff(int i, int j) {
    root(i); /* pot_diffs[i] := diff from root */
    root(j); /* pot_diffs[j] := diff from root */
    return adder(pot_diffs[i], inverser(pot_diffs[j]));
  }
};
using unionfind=UnionFind<>;
/*? end "uf.hpp" */

template<class EdgeVal>
struct Edge {
  int from; int to;
  EdgeVal weight;

  Edge(int from, int to, EdgeVal weight): from(from), to(to), weight(weight) {}
  IL bool operator==(CS Edge&e)CS{RT weight==e.weight&&from==e.from&&to==e.to;}
  IL bool operator<(CS Edge&e)CS{RT weight<e.weight||(weight==e.weight&&(from<e.from||(from==e.from&&to<e.to)));}
  IL bool operator<=(CS Edge&e)CS{RT this==e||this<e;}
  IL bool operator>(CS Edge&e)CS{RT e<this;}
  IL bool operator>=(CS Edge&e)CS{RT e<=this;}
};

template<class VtxVal, class EdgeVal>
class Graph {
  using VoidWithoutEdgeVal=TN enable_if<is_default_constructible<EdgeVal>::value,void>::type;
protected:
  int nv_, nde_;
  unionfind uf;
public:
  vec<VtxVal> vs;
  vvec<Edge<EdgeVal>> edges;

  Graph(int nv): nv_(nv), nde_(0), uf(nv), vs(nv), edges(nv) {}

  IL int nv()CS{RT nv_;}
  IL int nde()CS{RT nde_;}
  IL int nue()CS{RT nde_/2;}

  IL void add_dedge(int i, int j, const EdgeVal& val) {
    if(!rab::is_in(i, 0LL, nv_) || !rab::is_in(j, 0LL, nv_)) {
      cerr << "invalid index: (" << i << ", " << j << ") for Graph(nv = " << nv_ << ")" ln;
      exit(1);
    }
    edges[i].emplace_back(i, j, val);
    ++nde_;
  }
  IL VoidWithoutEdgeVal add_dedge(int i, int j) {
    add_dedge(i, j, EdgeVal());
  }

  IL void add_uedge(int i, int j, const EdgeVal& val) {
    add_dedge(i, j, val);
    add_dedge(j, i, val);
  }
  IL VoidWithoutEdgeVal add_uedge(int i, int j) {
    add_uedge(i, j, EdgeVal());
  }

  IL bool is_connected(){
    uf.clear();
    for(CS auto&es:edges)for(CS auto&e:es)uf.merge(e.from,e.to);
    RT uf.is_all_same();
  }
};
/*? end "graph.hpp" */
/*? begin "flow.hpp" */
/*!Arihon,https://tubo28.me/algorithm/dinic/*/
TL<TN F,TN V,TN E,TN CapFn=rab::identity>
/*F:通常int,CapFn:E->F*/
struct dinic{int n,s,t;VI level,prog,que;
WI edges;/*both direction*/
vvec<F>cap,flow;
dinic(CS Graph<V,E>&g,CS CapFn&capfn=rab::identity()):
n(g.nv()),s(-1),t(-1),level(n),prog(n),que(n+1),edges(n),cap(n,VI(n)),flow(n,VI(n))
{times(n,i){for(auto&e:g.edges[i]){F c=capfn(e.weight);
cap[i][e.to]+=c;cap[e.to][i]+=c;flow[e.to][i]+=c;edges[i].PB(e.to);
edges[e.to].PB(i);
}}}
F exec(int s,int t){this->s=s;this->t=t;F mf=0;
while(update_level(),level[t]>0){fill(iter(prog),0);mf+=find_paths(s,numeric_limits<F>::max()/*inf*/);
}
RT mf;
}
void update_level(){int ql=0,qr=0;fill(iter(level),-1);level[s]=0;
que[qr++]=s;while(ql!=qr/*queue is not empty*/){int v=que[ql++];
if(v==t)break;
for(CS int&d:edges[v]){if(level[d]<0&&cap[v][d]!=flow[v][d]){level[d]=level[v]+1;
que[qr++]=d;
}}}}
F find_paths(int v,int limit){if(v==t)RT limit;F diff=0;
for(;prog[v]<size(edges[v]);++prog[v]){int d=edges[v][prog[v]];
if(cap[v][d]!=flow[v][d]&&level[v]<level[d]){F df=find_paths(d,min(limit,cap[v][d]-flow[v][d]));
flow[v][d]+=df;flow[d][v]-=df;diff+=df;limit-=df;if(limit==0)break;
}}
RT diff;}};
/*? end "flow.hpp" */

void solve() {
// NMDM(-U-VPQW)
/* <foxy.memo-area> */
int N;int M;int D;cin>>N;cin>>M;cin>>D;VI U(M);VI V(M);VI P(M);VI Q(M);VI W(M);
times(M,Ri_0){cin>>U[Ri_0];--U[Ri_0];cin>>V[Ri_0];--V[Ri_0];cin>>P[Ri_0];cin>>Q[
Ri_0];cin>>W[Ri_0];}
/* </foxy.memo-area> */

  VPII vs; vs.reserve(M * 2);
  times(M, i) {
    vs.PB({U[i], P[i]});
    vs.PB({V[i], Q[i] + D});
  }
  auto cp = rab::compressed(vs);

  Graph<unit, int> g(cp.size);
  times(M, i) {
    g.add_dedge(cp.zip[{U[i], P[i]}], cp.zip[{V[i], Q[i] + D}], W[i]);
  }

  times(cp.size - 1, i) {
    if(cp.unzip[i].first == cp.unzip[i + 1].first) {
      g.add_dedge(i, i + 1, 1ll << 50);
    }
  }

  if(debug) {
    for(auto &es : g.edges) {
      for(auto &e : es) {
        cout << "(" << e.from sp << e.to sp << e.weight << ")" tb;
      }
      cout ln;
    }
  }

  dinic<int, unit, int> d(g);
  cout << d.exec(0, cp.size - 1) ln;
}

yukicoder

結果

テストケース

ソースコード