結果

問題 No.654 Air E869120
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-02-23 23:21:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,906 bytes
コンパイル時間 6,514 ms
コンパイル使用メモリ 106,564 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-10 03:16:12
合計ジャッジ時間 5,554 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,636 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 8 ms
6,816 KB
testcase_11 AC 7 ms
6,820 KB
testcase_12 AC 6 ms
6,820 KB
testcase_13 AC 7 ms
6,816 KB
testcase_14 AC 6 ms
6,816 KB
testcase_15 AC 6 ms
6,816 KB
testcase_16 AC 7 ms
6,820 KB
testcase_17 AC 7 ms
6,816 KB
testcase_18 AC 7 ms
6,816 KB
testcase_19 AC 7 ms
6,816 KB
testcase_20 AC 6 ms
6,816 KB
testcase_21 AC 6 ms
6,816 KB
testcase_22 AC 6 ms
6,816 KB
testcase_23 AC 6 ms
6,820 KB
testcase_24 AC 6 ms
6,820 KB
testcase_25 AC 6 ms
6,820 KB
testcase_26 AC 6 ms
6,816 KB
testcase_27 AC 6 ms
6,816 KB
testcase_28 AC 6 ms
6,816 KB
testcase_29 AC 5 ms
6,820 KB
testcase_30 TLE -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void add_edge(int, int, lint)':
main.cpp:28:45: warning: narrowing conversion of 'G[to].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   28 |   G[from].push_back((edge){to,cap,G[to].size()});
      |                                   ~~~~~~~~~~^~
main.cpp:29:47: warning: narrowing conversion of '(G[from].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   29 |   G[to].push_back((edge){from,0,G[from].size()-1});
      |                                 ~~~~~~~~~~~~~~^~

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<cassert>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

struct edge{
  int to;
  lint cap;
  int rev;
};
const int N=3001;

const lint INF=1e16;

// 蟻本p.195から
vector<edge>G[N];
int level[N];
int iter[N];
void add_edge(int from,int to,lint cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int>que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int i=0;i<(int)G[v].size();++i){
      edge&e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
	level[e.to]=level[v]+1;
	que.push(e.to);
      }
    }
  }
}

lint dfs(int v,int t,lint f){
  if(v==t)return f;
  for(int &i=iter[v];i<(int)G[v].size();++i){
    edge&e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

lint max_flow(int s,int t){
  lint flow=0;
  for(;;){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    lint f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

typedef pair<int,pii> pipii;
map<pipii,int> memo;

int get(int v,pii t){
  pipii ind(v,t);
  if(memo.count(ind))return memo[ind];
  int s=memo.size();
  memo[ind]=s;
  return s;
}


const int A=1000;
vector<pii> leave[A];
vector<pii> arrive[A];

int u[A],v[A],p[A],q[A],w[A];

int main(){
  int n,m,d;
  cin>>n>>m>>d;
  rep(i,m){
    cin>>u[i]>>v[i]>>p[i]>>q[i]>>w[i];
    u[i]--,v[i]--;
    leave[u[i]].push_back(pii(p[i],i));
    arrive[v[i]].push_back(pii(q[i],i));
    get(u[i],pii(p[i],i));
  }
  rep(i,n){
    get(n+v[i],pii(p[i],i));
  }
  assert((int)memo.size()<=N-2);
  rep(i,n){
    sort(leave[i].begin(),leave[i].end());
    sort(arrive[i].begin(),arrive[i].end());
  }
  rep(i,n){
    rep(j,leave[i].size()-1){
      int a=get(i,leave[i][j]);
      int b=get(i,leave[i][j+1]);
      add_edge(a,b,INF);
    }
    rep(j,arrive[i].size()){
      int a=get(n+i,arrive[i][j]);
      lint time=arrive[i][j].first;
      lint dst=time+d;
      if(dst>1e9)continue;
      int idx=lower_bound(leave[i].begin(),leave[i].end(),pii((int)dst,-1))-leave[i].begin();
      if(idx<(int)leave[i].size()){
	int b=get(i,leave[i][idx]);
	add_edge(a,b,INF);
      }
    }
  }
  rep(i,m){
    int a=get(u[i],pii(p[i],i));
    int b=get(n+v[i],pii(q[i],i));
    add_edge(a,b,w[i]);
  }
  int src=N-2;
  int sink=N-1;
  rep(i,arrive[n-1].size()){
    int a=get(n+n-1,arrive[n-1][i]);
    add_edge(a,sink,INF);
  }
  rep(i,leave[0].size()){
    int a=get(0,leave[0][i]);
    add_edge(src,a,INF);
  }
  lint flow=max_flow(src,sink);
  cout<<flow<<endl;
}
0