Submission #105561

#	Time	Username	Problem	Language	Result	Execution time	Memory
105561		Pro_ktmr	버스 (JOI14_bus)	C++14	100 / 100	749 ms	46940 KiB

bus

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

struct bus{
public:
	int begin,end,from,to;
};

int N,M,Q;
vector<pair<pair<int,int>,pair<int,int> > > node2[100000];
vector<bus> node[100000];
vector<int> depart[100000];
map<int,int> dp[100000];

int solve(int now, int t){ //nowを時刻t以降に出発する場合
	if(now == N-1) return t;
	int idx = lower_bound(depart[now].begin(), depart[now].end(), t) - depart[now].begin();
	if(idx == depart[now].size()) return INT_MAX;
	if(depart[now][idx] == t){
		if(dp[now].count(t) == 1) return dp[now][t];
		int ans = INT_MAX;
		while(idx < depart[now].size() && depart[now][idx] == t){
			ans = min(ans, solve(node[now][idx].to, node[now][idx].end));
			idx++;
		}
		if(idx != depart[now].size()) ans = min(ans, solve(now, depart[now][idx]));
		return dp[now][t] = ans;
	}
	else{
		return solve(now, depart[now][idx]);
	}
}

//solve(0,t)がL以下となる最大のtを出力
bool isOK(int now, int key){
	if(solve(0,now) <= key) return true;
	else return false;
}
int binary_search(int ok, int ng, int key){
	if(ng-ok == 1) return ok;
	int mid = (ok+ng)/2;
	if(isOK(mid, key)) return binary_search(mid, ng, key);
	else return binary_search(ok, mid, key);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	cin >> N >> M;
	for(int i=0; i<M; i++){
		bus tmp;
		cin >> tmp.from >> tmp.to >> tmp.begin >> tmp.end;
		tmp.from--; tmp.to--;
		node2[tmp.from].push_back(MP(MP(tmp.begin, tmp.end), MP(tmp.from, tmp.to)));
	}
	for(int i=0; i<N; i++){
		sort(node2[i].begin(), node2[i].end());
		for(int j=0; j<node2[i].size(); j++){
			bus tmp;
			tmp.begin = node2[i][j].first.first;
			tmp.end = node2[i][j].first.second;
			tmp.from = node2[i][j].second.first;
			tmp.to = node2[i][j].second.second;
			node[i].push_back(tmp);
			depart[i].push_back(tmp.begin);
		}
		node2[i].clear();
	}
	
	cin >> Q;
	for(int i=0; i<Q; i++){
		int L;
		cin >> L;
		//solve(0,t)がL以下となる最大のtを出力
		if(solve(0,0) > L) cout << -1 << endl;
		else cout << binary_search(0, 86400000, L) << endl;
	}

	return 0;
}

Compilation message (stderr)

bus.cpp: In function 'int solve(int, int)':
bus.cpp:47:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == depart[now].size()) return INT_MAX;
     ~~~~^~~~~~~~~~~~~~~~~~~~~
bus.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx < depart[now].size() && depart[now][idx] == t){
         ~~~~^~~~~~~~~~~~~~~~~~~~
bus.cpp:55:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx != depart[now].size()) ans = min(ans, solve(now, depart[now][idx]));
      ~~~~^~~~~~~~~~~~~~~~~~~~~
bus.cpp: In function 'int main()':
bus.cpp:89:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<node2[i].size(); j++){
                ~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50