Submission #6776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
6776	2014-07-06T10:55:07 Z	woqja125	버스 (JOI14_bus)	C++	100 / 100	260 ms	17012 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4724 KB	Output is correct
2	Correct	0 ms	4724 KB	Output is correct
3	Correct	0 ms	4724 KB	Output is correct
4	Correct	0 ms	4724 KB	Output is correct
5	Correct	0 ms	4724 KB	Output is correct
6	Correct	0 ms	4724 KB	Output is correct
7	Correct	0 ms	4724 KB	Output is correct
8	Correct	0 ms	4724 KB	Output is correct
9	Correct	0 ms	4724 KB	Output is correct
10	Correct	0 ms	4724 KB	Output is correct
11	Correct	0 ms	4724 KB	Output is correct
12	Correct	0 ms	4724 KB	Output is correct
13	Correct	0 ms	4784 KB	Output is correct
14	Correct	0 ms	4724 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4724 KB	Output is correct
2	Correct	28 ms	4724 KB	Output is correct
3	Correct	36 ms	4724 KB	Output is correct
4	Correct	0 ms	4724 KB	Output is correct
5	Correct	4 ms	4724 KB	Output is correct
6	Correct	0 ms	4724 KB	Output is correct
7	Correct	20 ms	4724 KB	Output is correct
8	Correct	0 ms	4724 KB	Output is correct
9	Correct	24 ms	4724 KB	Output is correct
10	Correct	36 ms	4724 KB	Output is correct
11	Correct	24 ms	4788 KB	Output is correct
12	Correct	36 ms	4724 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	236 ms	10664 KB	Output is correct
2	Correct	228 ms	10664 KB	Output is correct
3	Correct	216 ms	10664 KB	Output is correct
4	Correct	220 ms	10664 KB	Output is correct
5	Correct	224 ms	10664 KB	Output is correct
6	Correct	232 ms	10800 KB	Output is correct
7	Correct	208 ms	10672 KB	Output is correct
8	Correct	216 ms	11088 KB	Output is correct
9	Correct	244 ms	10836 KB	Output is correct
10	Correct	204 ms	11068 KB	Output is correct
11	Correct	188 ms	11200 KB	Output is correct
12	Correct	208 ms	11208 KB	Output is correct
13	Correct	192 ms	11208 KB	Output is correct
14	Correct	188 ms	11200 KB	Output is correct
15	Correct	184 ms	11204 KB	Output is correct
16	Correct	76 ms	17008 KB	Output is correct
17	Correct	72 ms	17008 KB	Output is correct

Subtask #4

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	256 ms	10664 KB	Output is correct
2	Correct	248 ms	10664 KB	Output is correct
3	Correct	228 ms	10664 KB	Output is correct
4	Correct	244 ms	10664 KB	Output is correct
5	Correct	244 ms	10664 KB	Output is correct
6	Correct	260 ms	10800 KB	Output is correct
7	Correct	232 ms	10672 KB	Output is correct
8	Correct	248 ms	10808 KB	Output is correct
9	Correct	240 ms	10836 KB	Output is correct
10	Correct	212 ms	11068 KB	Output is correct
11	Correct	240 ms	11200 KB	Output is correct
12	Correct	212 ms	11204 KB	Output is correct
13	Correct	236 ms	11204 KB	Output is correct
14	Correct	220 ms	11200 KB	Output is correct
15	Correct	232 ms	11204 KB	Output is correct
16	Correct	92 ms	17012 KB	Output is correct