oj.uz

Submission #105561

# Submission time Handle Problem Language Result Execution time Memory
105561 2019-04-13T13:40:26 Z Pro_ktmr 버스 (JOI14_bus) C++14
100 / 100
 749 ms 46940 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12160 KB Output is correct
2 Correct 15 ms 12288 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 16 ms 12132 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 13 ms 12160 KB Output is correct
7 Correct 15 ms 12160 KB Output is correct
8 Correct 15 ms 12160 KB Output is correct
9 Correct 15 ms 12160 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 23 ms 12288 KB Output is correct
13 Correct 17 ms 12672 KB Output is correct
14 Correct 15 ms 12544 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 324 ms 13716 KB Output is correct
3 Correct 295 ms 13876 KB Output is correct
4 Correct 37 ms 12288 KB Output is correct
5 Correct 37 ms 12348 KB Output is correct
6 Correct 30 ms 12288 KB Output is correct
7 Correct 199 ms 12792 KB Output is correct
8 Correct 14 ms 12160 KB Output is correct
9 Correct 174 ms 13048 KB Output is correct
10 Correct 314 ms 13916 KB Output is correct
11 Correct 176 ms 13304 KB Output is correct
12 Correct 559 ms 14300 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 38856 KB Output is correct
2 Correct 369 ms 38648 KB Output is correct
3 Correct 408 ms 38648 KB Output is correct
4 Correct 331 ms 38620 KB Output is correct
5 Correct 347 ms 38672 KB Output is correct
6 Correct 434 ms 39184 KB Output is correct
7 Correct 312 ms 38288 KB Output is correct
8 Correct 397 ms 43240 KB Output is correct
9 Correct 363 ms 39128 KB Output is correct
10 Correct 405 ms 44876 KB Output is correct
11 Correct 400 ms 45304 KB Output is correct
12 Correct 385 ms 44924 KB Output is correct
13 Correct 386 ms 45108 KB Output is correct
14 Correct 343 ms 44280 KB Output is correct
15 Correct 302 ms 44192 KB Output is correct
16 Correct 139 ms 39544 KB Output is correct
17 Correct 142 ms 39544 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 40280 KB Output is correct
2 Correct 478 ms 39900 KB Output is correct
3 Correct 745 ms 40312 KB Output is correct
4 Correct 740 ms 40420 KB Output is correct
5 Correct 471 ms 39840 KB Output is correct
6 Correct 610 ms 40516 KB Output is correct
7 Correct 718 ms 39980 KB Output is correct
8 Correct 677 ms 40696 KB Output is correct
9 Correct 683 ms 40668 KB Output is correct
10 Correct 732 ms 46616 KB Output is correct
11 Correct 645 ms 46860 KB Output is correct
12 Correct 720 ms 46940 KB Output is correct
13 Correct 692 ms 45776 KB Output is correct
14 Correct 715 ms 45880 KB Output is correct
15 Correct 749 ms 45856 KB Output is correct
16 Correct 332 ms 40432 KB Output is correct