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

• 問題: No.654 Air E869120
• ユーザー: hoget
• 提出日時: 2018-02-24 00:39:14
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 2,652 bytes
• コンパイル時間: 2,268 ms
• コンパイル使用メモリ: 179,148 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-18 17:51:26
• 合計ジャッジ時間: 3,770 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	9 ms; 5,376 KB
testcase_11	AC	9 ms; 5,376 KB
testcase_12	AC	8 ms; 5,376 KB
testcase_13	AC	9 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	9 ms; 5,376 KB
testcase_16	AC	12 ms; 5,376 KB
testcase_17	AC	13 ms; 5,376 KB
testcase_18	AC	12 ms; 5,376 KB
testcase_19	AC	11 ms; 5,376 KB
testcase_20	AC	6 ms; 5,376 KB
testcase_21	AC	7 ms; 5,376 KB
testcase_22	AC	4 ms; 5,376 KB
testcase_23	AC	5 ms; 5,376 KB
testcase_24	AC	6 ms; 5,376 KB
testcase_25	AC	4 ms; 5,376 KB
testcase_26	AC	6 ms; 5,376 KB
testcase_27	AC	5 ms; 5,376 KB
testcase_28	AC	5 ms; 5,376 KB
testcase_29	AC	5 ms; 5,376 KB
testcase_30	AC	4 ms; 5,376 KB
testcase_31	AC	4 ms; 5,376 KB
testcase_32	AC	4 ms; 5,376 KB
testcase_33	AC	5 ms; 5,376 KB
testcase_34	AC	4 ms; 5,376 KB
testcase_35	AC	3 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	2 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	2 ms; 5,376 KB

コンパイルメッセージ

main.cpp: In function 'void add_edge(long long int, long long int, long long int)':
main.cpp:35:51: warning: narrowing conversion of 'G[to].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   35 |         G[from].push_back((edge){to,cap,G[to].size()});
      |                                         ~~~~~~~~~~^~
main.cpp:36:54: warning: narrowing conversion of '(G[from].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   36 |         G[to].push_back((edge){from,0,G[from].size() - 1});
      |                                       ~~~~~~~~~~~~~~~^~~

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+15;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct edge{int to,cap,rev; };

vector<edge> G[20000];
int level[20000],iter[20000];

void add_edge(int from,int to,int 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 < 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);
			}
		}
	}
}

int dfs(int v,int t,int f){
	if(v == t) return f;
	for(int &i = iter[v];i < 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;
}

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

signed main(){
	int n,m,d,ans = 0,u[1000],v[1000],p[1000],q[1000],w[1000],cnt = 0;
	vector<int> tim[1000],ind[1000];
	cin >> n >> m >> d;
	for(int i = 0;i < m;i++){
		cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; u[i]--;v[i]--;q[i] += d;
		tim[u[i]].pb(p[i]);
		tim[v[i]].pb(q[i]);
	}
	for(int i = 0;i < n;i++){
		sort(all(tim[i]));
		tim[i].erase(unique(all(tim[i])),tim[i].end());
		for(int j = 0;j < tim[i].size();j++){
			if(j) add_edge(cnt - 1,cnt,INF);
			ind[i].pb(cnt++);
		}
	}
	for(int i = 0;i < m;i++){
		int ind1 = lower_bound(all(tim[u[i]]),p[i]) - tim[u[i]].begin();
		int ind2 = lower_bound(all(tim[v[i]]),q[i]) - tim[v[i]].begin();
		add_edge(ind[u[i]][ind1],ind[v[i]][ind2],w[i]);
	}
	if(ind[0].size() && ind[n - 1].size()) ans = max_flow(ind[0][0],ind[n - 1].back());
	cout << ans << endl;
	return 0;
}