oj.uz

Submission #749131

# Submission time Handle Problem Language Result Execution time Memory
749131 2023-05-27T11:40:03 Z Alan 버스 (JOI14_bus) C++17
100 / 100
 319 ms 24928 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct edge {
	int v, s, t;
	bool operator< (edge b) const {
		if (s != b.s) return s < b.s;
		if (t != b.t) return t < b.t;
		return v < b.v;
	}
};
 
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 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 22 ms 5780 KB Output is correct
3 Correct 29 ms 5708 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 14 ms 5552 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 16 ms 5708 KB Output is correct
10 Correct 23 ms 6728 KB Output is correct
11 Correct 16 ms 5972 KB Output is correct
12 Correct 26 ms 6784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 24168 KB Output is correct
2 Correct 217 ms 24084 KB Output is correct
3 Correct 221 ms 24092 KB Output is correct
4 Correct 231 ms 24180 KB Output is correct
5 Correct 232 ms 24064 KB Output is correct
6 Correct 230 ms 24108 KB Output is correct
7 Correct 259 ms 23612 KB Output is correct
8 Correct 207 ms 22668 KB Output is correct
9 Correct 219 ms 24032 KB Output is correct
10 Correct 277 ms 23760 KB Output is correct
11 Correct 291 ms 23812 KB Output is correct
12 Correct 262 ms 23848 KB Output is correct
13 Correct 250 ms 23752 KB Output is correct
14 Correct 270 ms 23744 KB Output is correct
15 Correct 261 ms 23692 KB Output is correct
16 Correct 59 ms 20988 KB Output is correct
17 Correct 59 ms 20988 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 24772 KB Output is correct
2 Correct 238 ms 24476 KB Output is correct
3 Correct 226 ms 24872 KB Output is correct
4 Correct 223 ms 24928 KB Output is correct
5 Correct 213 ms 24452 KB Output is correct
6 Correct 222 ms 24456 KB Output is correct
7 Correct 270 ms 24464 KB Output is correct
8 Correct 220 ms 24696 KB Output is correct
9 Correct 218 ms 24668 KB Output is correct
10 Correct 294 ms 24464 KB Output is correct
11 Correct 282 ms 24500 KB Output is correct
12 Correct 290 ms 24608 KB Output is correct
13 Correct 281 ms 24404 KB Output is correct
14 Correct 298 ms 24468 KB Output is correct
15 Correct 319 ms 24396 KB Output is correct
16 Correct 81 ms 21280 KB Output is correct