Submission #6801

#	Time	Username	Problem	Language	Result	Execution time	Memory
6801		Qwaz	버스 (JOI14_bus)	C++98	100 / 100	232 ms	17136 KiB

bus

#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;
}

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