Submission #748642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748642	2023-05-26T16:50:19 Z	Alan	버스 (JOI14_bus)	C++17	0 / 100	258 ms	24932 KB

bus

#include <bits/stdc++.h>
using namespace std;

struct edge {
	int v, s, t;
	bool operator< (edge b) const {return s < b.s;}
};

set<edge> G[100005];
int mn[100005];
const int inf = 1e9;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<pair<int, int>> ans;
	vector<edge> head;
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, s, t;
		cin >> u >> v >> s >> t;
		if (u == 1) head.push_back({v, s, t});
		else G[u].insert({v, s, t});
	}
	sort(head.begin(), head.end(), [&] (edge a, edge b) {return a.t > b.t;});
	for (int i = 1; i <= n; i++) mn[i] = inf;
	for (auto [r, x, y] : head) {
		mn[r] = y;
		function<void (int)> dfs = [&] (int u) {
			auto it = G[u].lower_bound({0, mn[u], 0});
			while (it != G[u].end()) {
				auto [v, s, t] = *it;
				it = G[u].erase(it);
				if (t >= mn[v]) continue;
				mn[v] = t;
				dfs(v);
			}
		};
		dfs(r);
		if (mn[n] != inf && (ans.empty() || mn[n] < ans.back().first)) ans.push_back({mn[n], x});
	}
	reverse(ans.begin(), ans.end());
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		auto iter = upper_bound(ans.begin(), ans.end(), pair<int, int>{t, inf});
		if (iter == ans.begin()) cout << "-1\n";
		else cout << (--iter)->second << '\n';
	}

	return 0;
}

Subtask #1

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4948 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Incorrect	23 ms	5784 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	24092 KB	Output is correct
2	Correct	209 ms	24152 KB	Output is correct
3	Correct	220 ms	24208 KB	Output is correct
4	Correct	211 ms	24116 KB	Output is correct
5	Correct	218 ms	24264 KB	Output is correct
6	Correct	225 ms	23948 KB	Output is correct
7	Incorrect	258 ms	23628 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	24732 KB	Output is correct
2	Correct	227 ms	24364 KB	Output is correct
3	Correct	227 ms	24800 KB	Output is correct
4	Correct	253 ms	24932 KB	Output is correct
5	Correct	216 ms	24416 KB	Output is correct
6	Incorrect	223 ms	24584 KB	Output isn't correct
7	Halted	0 ms	0 KB	-