Submission #6776

#	Time	Username	Problem	Language	Result	Execution time	Memory
6776		woqja125	버스 (JOI14_bus)	C++98	100 / 100	260 ms	17012 KiB

bus

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
struct bus
{
	int e, st, et;
};
bool operator<(const bus &A, const bus &B)
{
	return A.st<B.st;
}
std::priority_queue<bus> map[100001];
struct an
{
	int st, et;
};
bool operator<(const an &A, const an &B)
{
	return A.et>B.et;
}
std::vector<an> ans;
int n;
int v[100001];
int dfs(int x, int t)
{
	if(x==n) return t;
	int &m = v[x];
	while(!map[x].empty() && map[x].top().st >= t)
	{
		bus t = map[x].top();
		map[x].pop();
		int r = dfs(t.e, t.et);
		if(r < m) m = r;
	}
	return m;
}
int main()
{
	int m, a, x, b, y, i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++)
	{
		scanf("%d%d%d%d", &a, &b, &x, &y);
		map[a].push({b, x, y});
	}
	for(i=1; i<=n; i++) v[i] = 2147483647;
	while(!map[1].empty())
	{
		int st = map[1].top().st;
		int r = dfs(1, st);
		ans.push_back({st, r});
	}
	scanf("%d", &a);
	for(i=1; i<=a; i++)
	{
		scanf("%d", &x);
		an t;
		t.et = x;	t.st = 0;
		std::vector<an>::iterator it = std::lower_bound(ans.begin(), ans.end(), t);
		if(it == ans.end()) printf("-1\n");
		else printf("%d\n", (it)->st);
	}
	return 0;
}

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