답안 #6801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6801 2014-07-07T14:42:15 Z Qwaz 버스 (JOI14_bus) C++
100 / 100
232 ms 17136 KB
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair < int, int > pii;
const int MAX = 300020, INF = 123456789;

struct bus {
	int s, t, sTime, eTime;

	bus() {}
	bus(int s, int t, int sTime, int eTime) : s(s), t(t), sTime(sTime), eTime(eTime) {}

	bool operator < (const bus &t) const {
		return eTime < t.eTime;
	}
};

int n, m, numQuery, query[MAX];
bus data[MAX];

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i = 0; i<m; i++){
		int a, b, x, y;
		scanf("%d%d%d%d", &a, &b, &x, &y);
		data[i] = bus(a, b, x, y);
	}

	sort(data, data+m);

	scanf("%d", &numQuery);
	for(i = 0; i<numQuery; i++)
		scanf("%d", &query[i]);
}

//(도달시간, 출발시간)
vector < pii > time[MAX];

int getLast(int target, int t){
	pii find = pii(t+1, 0);
	vector < pii > &v = time[target];

	if(v.size() == 0) return -INF;

	int index = lower_bound(v.begin(), v.end(), find)-v.begin();
	if(index == 0) return -INF;

	return v[index-1].second;
}

void solve(){
	time[1].push_back(pii(0, 0));

	int i;
	for(i = 0; i<m; i++){
		bus &now = data[i];
		int last;

		if(now.s == 1) last = now.sTime;
		else last = getLast(now.s, now.sTime);

		if(last != -INF && (time[now.t].size() == 0 || time[now.t][time[now.t].size()-1].second < last))
			time[now.t].push_back(pii(now.eTime, last));
	}

	for(i = 0; i<numQuery; i++){
		int res = getLast(n, query[i]);
		printf("%d\n", res == -INF ? -1 : res);
	}
}

int main(){
	input();

	solve();

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14100 KB Output is correct
2 Correct 4 ms 14100 KB Output is correct
3 Correct 0 ms 14100 KB Output is correct
4 Correct 0 ms 14100 KB Output is correct
5 Correct 4 ms 14100 KB Output is correct
6 Correct 0 ms 14100 KB Output is correct
7 Correct 4 ms 14100 KB Output is correct
8 Correct 0 ms 14100 KB Output is correct
9 Correct 0 ms 14100 KB Output is correct
10 Correct 4 ms 14100 KB Output is correct
11 Correct 4 ms 14100 KB Output is correct
12 Correct 0 ms 14100 KB Output is correct
13 Correct 4 ms 14100 KB Output is correct
14 Correct 0 ms 14100 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14100 KB Output is correct
2 Correct 32 ms 14100 KB Output is correct
3 Correct 36 ms 14100 KB Output is correct
4 Correct 0 ms 14100 KB Output is correct
5 Correct 4 ms 14100 KB Output is correct
6 Correct 0 ms 14100 KB Output is correct
7 Correct 28 ms 14100 KB Output is correct
8 Correct 0 ms 14100 KB Output is correct
9 Correct 28 ms 14100 KB Output is correct
10 Correct 36 ms 14100 KB Output is correct
11 Correct 24 ms 14100 KB Output is correct
12 Correct 40 ms 14100 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 14100 KB Output is correct
2 Correct 168 ms 14100 KB Output is correct
3 Correct 180 ms 14100 KB Output is correct
4 Correct 192 ms 14100 KB Output is correct
5 Correct 180 ms 14100 KB Output is correct
6 Correct 172 ms 14232 KB Output is correct
7 Correct 188 ms 14496 KB Output is correct
8 Correct 200 ms 15156 KB Output is correct
9 Correct 192 ms 14232 KB Output is correct
10 Correct 188 ms 14232 KB Output is correct
11 Correct 176 ms 14232 KB Output is correct
12 Correct 196 ms 14232 KB Output is correct
13 Correct 184 ms 14232 KB Output is correct
14 Correct 180 ms 14100 KB Output is correct
15 Correct 180 ms 14232 KB Output is correct
16 Correct 68 ms 17136 KB Output is correct
17 Correct 68 ms 17136 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 14100 KB Output is correct
2 Correct 200 ms 14100 KB Output is correct
3 Correct 224 ms 14100 KB Output is correct
4 Correct 220 ms 14100 KB Output is correct
5 Correct 216 ms 14100 KB Output is correct
6 Correct 220 ms 14232 KB Output is correct
7 Correct 224 ms 14496 KB Output is correct
8 Correct 204 ms 14232 KB Output is correct
9 Correct 232 ms 14232 KB Output is correct
10 Correct 212 ms 14232 KB Output is correct
11 Correct 216 ms 14232 KB Output is correct
12 Correct 208 ms 14232 KB Output is correct
13 Correct 204 ms 14232 KB Output is correct
14 Correct 216 ms 14100 KB Output is correct
15 Correct 192 ms 14232 KB Output is correct
16 Correct 92 ms 17136 KB Output is correct