#238437 (C++17) No.654 Air E869120

提出ソース

結果

問題	No.654 Air E869120
ユーザー	WA_TLE
提出日時	2018-02-23 23:19:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	3,812 bytes
コンパイル時間	2,109 ms
コンパイル使用メモリ	162,028 KB
実行使用メモリ	35,200 KB
最終ジャッジ日時	2024-10-10 03:04:24
合計ジャッジ時間	4,750 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,816 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,816 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	110 ms 35,200 KB
testcase_11	AC	85 ms 35,200 KB
testcase_12	AC	85 ms 35,072 KB
testcase_13	AC	103 ms 35,072 KB
testcase_14	AC	87 ms 35,200 KB
testcase_15	AC	83 ms 35,072 KB
testcase_16	AC	46 ms 35,072 KB
testcase_17	AC	51 ms 35,072 KB
testcase_18	AC	48 ms 35,200 KB
testcase_19	AC	48 ms 35,200 KB
testcase_20	AC	33 ms 35,200 KB
testcase_21	AC	34 ms 35,072 KB
testcase_22	AC	30 ms 35,200 KB
testcase_23	AC	33 ms 35,072 KB
testcase_24	AC	33 ms 35,072 KB
testcase_25	AC	29 ms 35,072 KB
testcase_26	AC	31 ms 35,200 KB
testcase_27	AC	30 ms 35,200 KB
testcase_28	AC	31 ms 34,944 KB
testcase_29	AC	31 ms 35,072 KB
testcase_30	AC	30 ms 35,072 KB
testcase_31	AC	32 ms 35,200 KB
testcase_32	AC	31 ms 35,200 KB
testcase_33	RE	-
testcase_34	AC	28 ms 35,072 KB
testcase_35	AC	2 ms 6,816 KB
testcase_36	AC	2 ms 6,816 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	2 ms 6,820 KB
testcase_39	AC	2 ms 6,816 KB

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

ソースコード

raw source code

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;

const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
class dinic{
public:
	int n,sta,gol;
	vector<vector<llint>> hen;
	vector<int>dis;//bfsの距離
	//隣接行列(O(VVE)なので)
	vector<set<int>>tna;
	//hen[town][i]>0 を探す
	dinic(int in,int s,int g){
		n=in;
		sta=s;
		gol=g;
		hen.res(in);
		dis.res(in);
		tna.res(in);
		for(int i=0;i<n;i++){hen[i].res(in);}
	}
	void add(int u,int v,llint wei){hen[u][v]+=wei;tna[u].ins(v);}
	//隣接なので逆編情報が不要!!
	//増加のbfsする
	//それが増加する向きだけに流す
	//流れないなら、終了!
	void bfs(void){
		int i;
		for(i=0;i<n;i++){dis[i]=-1;}//初期化
		queue<pair<int,int>>que;
		que.push(mp(0,sta));
		dis[sta]=0;
		while(!que.empty()){
			
			int kyo=que.front().fir;
			int town=que.front().sec;
			que.pop();
			for(auto i:tna[town]){
				if(hen[town][i]!=0&&dis[i]==-1){dis[i]=kyo+1;que.push(mp(kyo+1,i));}
			}
		}
	}
	llint dfs(int ter,llint lim){
		//それまでの上限がlim
		//流した量を返す
		if(ter==gol){return lim;}
		llint ans=0;
		for(auto i:tna[ter]){
			if(dis[ter]>=dis[i]||hen[ter][i]==0){continue;}//dinic
			if(lim==ans){break;}
			llint nga=dfs(i,min(lim-ans,hen[ter][i]));
			ans+=nga;
			hen[ter][i]-=nga;
			hen[i][ter]+=nga;
			tna[i].ins(ter);
		}
		return ans;
	}
	llint solve(void){
		llint ans=0;
		while(-1){
			bfs();
			llint nga=dfs(sta,big);
			ans+=nga;
			if(nga==0){break;}
		}
		return ans;
	}
};
int main(void){
	//♨♨フロー♨♨
	//はいフロー 貼るだけ界のtourist
	llint n,m,d,i,j;cin>>n>>m>>d;
	dinic gra(m+m,0,0);
	vector<vector<pair<llint,llint>>> zyu(n);
	for(i=0;i<m;i++){
		llint u,v,p,q,w;cin>>u>>v>>p>>q>>w;u--;v--;q+=d;
		gra.add(i+m,i,w);
		zyu[u].pub(mp(p,i+m));
		zyu[v].pub(mp(q,i));
	}
	for(i=0;i<n;i++){SO(zyu[i]);}
	for(i=0;i<n;i++){
		for(j=1;j<zyu[i].size();j++){
			gra.add(zyu[i][j-1].sec,zyu[i][j].sec,big);
		}
	}
	gra.sta=zyu[0][0].sec;
	gra.gol=zyu.back().back().sec;
	cout<<gra.solve()<<endl;RE;
}

yukicoder

結果

テストケース

ソースコード