第2回 ドワンゴからの挑戦状 予選

Submission #1334268

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
struct edge{int to,cost,num,pre,dir;};
int n,m,s,t,dist[30000],dp[30000];vector<edge>x[30000];vector<int>F[30000],G[30000],H[30000];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Q;
bool solve(int p){
	if(p<0)return false;
	for(int i=0;i<n;i++)dp[i]=1e9;
	dp[s]=0;Q.push(make_pair(0,s));
	while(!Q.empty()){
		int a1=Q.top().first,a2=Q.top().second;Q.pop();
		for(int i=0;i<x[a2].size();i++){
			int to1=x[a2][i].to,cost1=x[a2][i].cost;
			int D=0;
			if(x[a2][i].dir==1){
				D=dist[F[x[a2][i].num][0]];
				D+=H[x[a2][i].num][x[a2][i].pre];
			}
			if(x[a2][i].dir==0){
				D=dist[F[x[a2][i].num][F[x[a2][i].num].size()-1]];
				D+=H[x[a2][i].num][H[x[a2][i].num].size()-1]-H[x[a2][i].num][x[a2][i].pre];
			}
			if(D+a1>p)continue;
			if(dp[to1]>a1+cost1){
				dp[to1]=a1+cost1;Q.push(make_pair(dp[to1],to1));
			}
		}
	}
	if(dp[t]<5e8)return true;
	return false;
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=0;i<m;i++){
		int a;cin>>a;
		for(int j=0;j<a;j++){int b;cin>>b;F[i].push_back(b);}
		for(int j=0;j<a-1;j++){int b;cin>>b;G[i].push_back(b);}
		H[i].push_back(0);for(int j=0;j<G[i].size();j++)H[i].push_back(H[i][j]+G[i][j]);
		for(int j=0;j<a-1;j++){
			x[F[i][j]].push_back(edge{F[i][j+1],G[i][j],i,j,0});
			x[F[i][j+1]].push_back(edge{F[i][j],G[i][j],i,j+1,1});
		}
	}
	for(int i=0;i<n;i++)dist[i]=1e9;
	dist[t]=0;Q.push(make_pair(0,t));
	while(!Q.empty()){
		int a1=Q.top().first,a2=Q.top().second;Q.pop();
		for(int i=0;i<x[a2].size();i++){
			if(dist[x[a2][i].to]>dist[a2]+x[a2][i].cost){
				dist[x[a2][i].to]=dist[a2]+x[a2][i].cost;
				Q.push(make_pair(dist[x[a2][i].to],x[a2][i].to));
			}
		}
	}
	int L=0,R=500000000,M;
	while(true){
		M=(L+R)/2;
		bool p1=solve(M-1),p2=solve(M);
		if(p1==false && p2==true){cout<<M<<endl;return 0;}
		if(p1==true)R=M;else L=M;
	}
	return 0;
}

Submission

Task問題 C - メンテナンス明け
User nameユーザ名 E869120
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1935 Byte
File nameファイル名
Exec time実行時間 363 ms
Memory usageメモリ使用量 7040 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 small/00_sample00,small/00_sample01,small/00_sample02,small/10_small-0000,small/10_small-0001,small/10_small-0002,small/10_small-0003,small/10_small-0004,small/10_small-0005,small/10_small-0006,small/10_small-0007,small/10_small-0008,small/10_small-0009,small/10_small-0010,small/10_small-0011,small/10_small-0012,small/10_small-0013,small/10_small-0014,small/10_small-0015,small/10_small-0016,small/10_small-0017,small/10_small-0018,small/10_small-0019,small/30_max_small,small/40_simple_0000,small/40_simple_0001,small/40_simple_0002,small/40_simple_0003,small/40_simple_0004,small/40_simple_0005,small/40_simple_0006,small/40_simple_0007,small/40_simple_0008,small/40_simple_0009,small/40_simple_0010,small/40_simple_0011,small/40_simple_0012,small/40_simple_0013,small/40_simple_0014,small/40_simple_0015,small/40_simple_0016,small/40_simple_0017,small/40_simple_0018,small/40_simple_0019,small/90_dijkstra_killer_00,small/90_dijkstra_killer_01,small/91_tayama_killer_00,small/91_tayama_killer_01,small/91_tayama_killer_02,small/91_tayama_killer_03,small/91_tayama_killer_04,small/91_tayama_killer_05
Subtask2 50 / 50 large/20_large-00,large/20_large-01,large/20_large-02,large/20_large-03,large/20_large-04,large/31_max_large

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
large/20_large-00 AC 298 ms 6912 KB
large/20_large-01 AC 309 ms 7040 KB
large/20_large-02 AC 363 ms 7040 KB
large/20_large-03 AC 288 ms 6912 KB
large/20_large-04 AC 318 ms 6912 KB
large/31_max_large AC 45 ms 4736 KB
small/00_sample00 AC 3 ms 3072 KB
small/00_sample01 AC 3 ms 3072 KB
small/00_sample02 AC 3 ms 3072 KB
small/10_small-0000 AC 5 ms 3072 KB
small/10_small-0001 AC 4 ms 3072 KB
small/10_small-0002 AC 4 ms 3072 KB
small/10_small-0003 AC 4 ms 3072 KB
small/10_small-0004 AC 4 ms 3072 KB
small/10_small-0005 AC 4 ms 3072 KB
small/10_small-0006 AC 4 ms 3072 KB
small/10_small-0007 AC 4 ms 3072 KB
small/10_small-0008 AC 4 ms 3072 KB
small/10_small-0009 AC 4 ms 3072 KB
small/10_small-0010 AC 4 ms 3072 KB
small/10_small-0011 AC 4 ms 3072 KB
small/10_small-0012 AC 4 ms 3072 KB
small/10_small-0013 AC 4 ms 3072 KB
small/10_small-0014 AC 4 ms 3072 KB
small/10_small-0015 AC 4 ms 3072 KB
small/10_small-0016 AC 4 ms 3072 KB
small/10_small-0017 AC 4 ms 3072 KB
small/10_small-0018 AC 4 ms 3072 KB
small/10_small-0019 AC 4 ms 3072 KB
small/30_max_small AC 3 ms 3072 KB
small/40_simple_0000 AC 2 ms 3072 KB
small/40_simple_0001 AC 3 ms 3072 KB
small/40_simple_0002 AC 2 ms 3072 KB
small/40_simple_0003 AC 3 ms 3072 KB
small/40_simple_0004 AC 3 ms 3072 KB
small/40_simple_0005 AC 3 ms 3072 KB
small/40_simple_0006 AC 3 ms 3072 KB
small/40_simple_0007 AC 3 ms 3072 KB
small/40_simple_0008 AC 3 ms 3072 KB
small/40_simple_0009 AC 3 ms 3072 KB
small/40_simple_0010 AC 3 ms 3072 KB
small/40_simple_0011 AC 3 ms 3072 KB
small/40_simple_0012 AC 3 ms 3072 KB
small/40_simple_0013 AC 3 ms 3072 KB
small/40_simple_0014 AC 3 ms 3072 KB
small/40_simple_0015 AC 3 ms 3072 KB
small/40_simple_0016 AC 3 ms 3072 KB
small/40_simple_0017 AC 3 ms 3072 KB
small/40_simple_0018 AC 3 ms 3072 KB
small/40_simple_0019 AC 3 ms 3072 KB
small/90_dijkstra_killer_00 AC 3 ms 3072 KB
small/90_dijkstra_killer_01 AC 3 ms 3072 KB
small/91_tayama_killer_00 AC 3 ms 3072 KB
small/91_tayama_killer_01 AC 3 ms 3072 KB
small/91_tayama_killer_02 AC 3 ms 3072 KB
small/91_tayama_killer_03 AC 3 ms 3072 KB
small/91_tayama_killer_04 AC 3 ms 3072 KB
small/91_tayama_killer_05 AC 3 ms 3072 KB