#308977 (Java21) No.654 Air E869120

提出ソース

結果

問題	No.654 Air E869120
ユーザー	SJiro64
提出日時	2019-01-08 11:33:19
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	5,117 bytes
コンパイル時間	2,407 ms
コンパイル使用メモリ	80,396 KB
実行使用メモリ	58,608 KB
最終ジャッジ日時	2024-11-24 00:36:43
合計ジャッジ時間	12,422 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	140 ms 41,484 KB
testcase_01	AC	137 ms 41,700 KB
testcase_02	AC	151 ms 41,824 KB
testcase_03	AC	139 ms 41,724 KB
testcase_04	AC	153 ms 41,972 KB
testcase_05	AC	140 ms 41,524 KB
testcase_06	AC	150 ms 41,728 KB
testcase_07	AC	141 ms 41,608 KB
testcase_08	AC	146 ms 41,348 KB
testcase_09	AC	142 ms 41,868 KB
testcase_10	AC	312 ms 47,092 KB
testcase_11	AC	288 ms 47,224 KB
testcase_12	AC	296 ms 47,324 KB
testcase_13	AC	292 ms 46,940 KB
testcase_14	AC	286 ms 47,304 KB
testcase_15	AC	295 ms 47,312 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	245 ms 46,716 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	248 ms 46,180 KB
testcase_26	WA	-
testcase_27	AC	244 ms 46,780 KB
testcase_28	WA	-
testcase_29	AC	243 ms 46,512 KB
testcase_30	AC	248 ms 46,592 KB
testcase_31	AC	252 ms 46,236 KB
testcase_32	AC	253 ms 46,768 KB
testcase_33	AC	257 ms 49,900 KB
testcase_34	AC	258 ms 46,688 KB
testcase_35	AC	116 ms 41,408 KB
testcase_36	AC	132 ms 41,340 KB
testcase_37	AC	116 ms 41,280 KB
testcase_38	AC	127 ms 41,316 KB
testcase_39	AC	143 ms 41,584 KB

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

ソースコード

raw source code

import java.util.*;
public class Main {
	static final int INF=Integer.MAX_VALUE;
	static boolean[] used;
	static int flow;
	
	static int V;//頂点
	static int E;//辺
	
	static List<List<edge>> G;//listの二重構造で隣接リスト実現

	static int N;
	static int M;//飛行機の便の数
	static int d;
	
	static int[]u;//uから
	static int[]v;//Vまで飛ぶ。
	static int[]p;//時刻pに離陸
	static int[]q;//時刻qに到着
	static int[]w;//飛行機に乗れる人数
	
	static List<List<Integer>>dic;
	static List<List<Integer>>dic2;
	
	static int[]sz;
	
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc= new Scanner(System.in);
		
		N= sc.nextInt();
		M= sc.nextInt();
		d= sc.nextInt();
		
		u= new int[M];
		v= new int[M];
		p= new int[M];
		q= new int[M];
		w= new int[M];
		
		
		//dic 作成
		dic= new ArrayList<>();
		for(int i=0;i<N;i++)	dic.add(new ArrayList<>());
		
		for(int i=0;i<M;i++){
			u[i]= sc.nextInt();
			v[i]= sc.nextInt();
			p[i]= sc.nextInt();
			q[i]= sc.nextInt();
			w[i]= sc.nextInt();
			
			//街を0オリジンで格納したい
			u[i]--;
			v[i]--;
			
			//Q+dに到着とすることで、乗り換えの時差を解決
			q[i]+= d;
			
			dic.get(u[i]).add(p[i]);
			dic.get(v[i]).add(q[i]);
		}
		
		sc.close();
		
		
		//dicをhashsetを使って座圧
		//dic2= new ArrayList<>(new LinkedHashSet<>(dic));これだとダメ、多分dic.get(i)[街]のところが座圧される　
		dic2= new ArrayList<>();
		
		for(int i=0;i<N;i++){
			List<Integer> hash= new ArrayList<>(new LinkedHashSet<>(dic.get(i)));
			Collections.sort(hash);
			dic2.add(hash);
		}
		
		
		//Gの作成
		sz= new int[N];//それぞれの街の頂点の累積和を記録[個]
		sz[0]=dic2.get(0).size();
		for(int i=1;i<N;i++)sz[i]=sz[i-1]+ dic2.get(i).size();
		
		V= sz[N-1];//全ての頂点の数[個]
		
		
		//使う頂点を一列の隣接リストGに変換したい
		G= new ArrayList<>();
		for(int i=0;i<= V;i++)G.add(new ArrayList<>());//全ての頂点を一列にした
		
		for(int i=0;i<N;i++){//行を繋げる
			int start=0;
			if(i > 0)start += sz[i-1];
			
			int n= dic2.get(i).size();//個
			
			//添字stから始まる、n個
			for(int j=0;j<n-1;j++){
				int from=start+ j;
				int to= from+ 1;
				add_edge(from,to,INF);
			}	
		}
		
		
		
		for(int i=0;i<M;i++){//移動辺を繋げる(G[u[i]][p[i]]→G[v[i]][q[i]])
			//G[u[i]][p[i]]の添字を探す
			
			//G.get(u[i])の位置
			int startU= 0;
			if(u[i]>0)startU= sz[u[i]-1];
			
			int u_p= lower_bound(dic2.get(u[i]),p[i]);//p[i]は街u[i]の中で何番目の頂点か
			
			int from= startU+ u_p;
			
			
			//G.get(v[i])の位置
			int startV=0;
			if(v[i]>0)startV= sz[v[i]-1];
			
			int v_q= lower_bound(dic2.get(v[i]),q[i]);//q[i]は街v[i]の中で何番目の頂点か
			
			int to= startV+ v_q;
			
			
			add_edge(from,to,w[i]);
		}
	
		//max_flow
		int ans= max_flow(0,V-1);//sz[]はそれぞれの街の頂点の"個数"の累積和だから、0origenでは-1
		System.out.println(ans);

	}
	
	static void add_edge(int from,int to,int cap){
		G.get(from).add(new edge(to,cap,G.get(to).size()));
		//同時に逆辺も辿れるようにするため、に双方向に紐をつける。
		G.get(to).add(new edge(from,0,G.get(from).size()-1));
	}
	
	static int lower_bound(List<Integer>A,int key){
		//binary_searchで実装。keyが街Aの何個目の要素か、indexを返す
				int left= 0;
				int right= A.size();
				int mid;
				
				while(left< right){
					mid= (left+ right)/2;
					if(A.get(mid) == key)return mid;

					if(key< A.get(mid))right= mid;
					if(A.get(mid)< key)left= mid+1;
				}
				
				return 0;//返せないことはあり得ないが、便宜上
	}


static int dfs(int v,int t,int f){
	if(v == t)return f;//tまでたどり着いた
	
	used[v] = true;
	
	for(int i=0;i<G.get(v).size();i++){
		edge e =G.get(v).get(i);
		
		if(used[e.to] != true && e.cap >0){
			int d= dfs(e.to,t,Math.min(f, e.cap));
			//min(f,e.cap)はまだ流す量を決めている段階。暫定の流量
			
			if(d>0){//tまでたどり着いた(流せる)時
			//v==tのreturn fを受けて、ここで初めてf(=d)を流す
				e.cap -=d;
				G.get(e.to).get(e.rev).cap += d;//直接逆辺のcを変化させて、
				return d;//各辺でdを流すために戻る。　
			}	
		}	
	}
		return 0;
		/* 
		 * tまでたどり着けなかった（途中の辺の容量が0だったのでdfs(e.to,cap,min(f,e.cap))でd=0が返ってくる）
		 * 最初f==INFだから、d==0(f==0)の時は、全ての辺を辿ってみたけど全く流せなかったってこと
		 * d>0に引っかからなかったとも言える
		 */
}
	

static int max_flow(int s,int t) {
	int flow= 0;
	
	while(true){
		used =new boolean[V];
		
		int f= dfs(s,t,INF);
		if(f == 0)return flow;//if(もうこれ以上流せない)return
		flow +=f;
	}
	
}

static class edge {
	int to;
	int cap;
	int rev;//逆辺にアクセスする
	
	edge(int to,int cap,int rev){
		this.to =to;
		this.cap =cap;
		this.rev =rev;
	}

}

}

yukicoder

結果

テストケース

ソースコード