oj.uz

Submission #748647

# Submission time Handle Problem Language Result Execution time Memory
748647 2023-05-26T16:53:20 Z Alan 버스 (JOI14_bus) C++17
85 / 100
 343 ms 24912 KB 
#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.s > b.s;});
	for (int i = 1; i <= n; i++) mn[i] = inf;
	for (auto [r, x, y] : head) if (mn[r] > y) {
		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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 5 ms 5076 KB Output is correct
13 Correct 3 ms 5332 KB Output is correct
14 Correct 6 ms 5024 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 20 ms 5748 KB Output is correct
3 Correct 23 ms 5720 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5096 KB Output is correct
6 Incorrect 4 ms 5076 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 24164 KB Output is correct
2 Correct 219 ms 24128 KB Output is correct
3 Correct 246 ms 24168 KB Output is correct
4 Correct 215 ms 24156 KB Output is correct
5 Correct 216 ms 24120 KB Output is correct
6 Correct 229 ms 23980 KB Output is correct
7 Correct 241 ms 23668 KB Output is correct
8 Correct 205 ms 22612 KB Output is correct
9 Correct 252 ms 24088 KB Output is correct
10 Correct 273 ms 23764 KB Output is correct
11 Correct 268 ms 23692 KB Output is correct
12 Correct 253 ms 23764 KB Output is correct
13 Correct 256 ms 23760 KB Output is correct
14 Correct 249 ms 23708 KB Output is correct
15 Correct 265 ms 23756 KB Output is correct
16 Correct 61 ms 20924 KB Output is correct
17 Correct 59 ms 20960 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 24680 KB Output is correct
2 Correct 251 ms 24416 KB Output is correct
3 Correct 253 ms 24800 KB Output is correct
4 Correct 263 ms 24912 KB Output is correct
5 Correct 262 ms 24444 KB Output is correct
6 Correct 253 ms 24396 KB Output is correct
7 Correct 317 ms 24424 KB Output is correct
8 Correct 251 ms 24572 KB Output is correct
9 Correct 248 ms 24728 KB Output is correct
10 Correct 343 ms 24536 KB Output is correct
11 Correct 340 ms 24484 KB Output is correct
12 Correct 317 ms 24544 KB Output is correct
13 Correct 319 ms 24432 KB Output is correct
14 Correct 326 ms 24484 KB Output is correct
15 Correct 310 ms 24472 KB Output is correct
16 Correct 83 ms 21184 KB Output is correct