oj.uz

Submission #749129

# Submission time Handle Problem Language Result Execution time Memory
749129 2023-05-27T11:38:58 Z Alan 버스 (JOI14_bus) C++17
85 / 100
 327 ms 34404 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;
		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 5028 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 3 ms 5036 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 5024 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 4 ms 5164 KB Output is correct
12 Correct 3 ms 5164 KB Output is correct
13 Correct 3 ms 5332 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5028 KB Output is correct
2 Correct 22 ms 6656 KB Output is correct
3 Correct 23 ms 6652 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Incorrect 4 ms 5040 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 246 ms 32744 KB Output is correct
2 Correct 217 ms 32912 KB Output is correct
3 Correct 214 ms 32752 KB Output is correct
4 Correct 213 ms 32836 KB Output is correct
5 Correct 215 ms 32728 KB Output is correct
6 Correct 209 ms 32556 KB Output is correct
7 Correct 254 ms 31664 KB Output is correct
8 Correct 213 ms 31240 KB Output is correct
9 Correct 218 ms 32684 KB Output is correct
10 Correct 325 ms 31124 KB Output is correct
11 Correct 264 ms 31224 KB Output is correct
12 Correct 269 ms 31244 KB Output is correct
13 Correct 282 ms 31156 KB Output is correct
14 Correct 291 ms 31180 KB Output is correct
15 Correct 279 ms 31204 KB Output is correct
16 Correct 62 ms 23368 KB Output is correct
17 Correct 67 ms 23508 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 34276 KB Output is correct
2 Correct 233 ms 33864 KB Output is correct
3 Correct 228 ms 34332 KB Output is correct
4 Correct 240 ms 34404 KB Output is correct
5 Correct 255 ms 33992 KB Output is correct
6 Correct 232 ms 33924 KB Output is correct
7 Correct 289 ms 33324 KB Output is correct
8 Correct 235 ms 34084 KB Output is correct
9 Correct 236 ms 34232 KB Output is correct
10 Correct 318 ms 32836 KB Output is correct
11 Correct 291 ms 32800 KB Output is correct
12 Correct 292 ms 32844 KB Output is correct
13 Correct 327 ms 32808 KB Output is correct
14 Correct 308 ms 32752 KB Output is correct
15 Correct 286 ms 32676 KB Output is correct
16 Correct 76 ms 24368 KB Output is correct