oj.uz

Submission #748639

# Submission time Handle Problem Language Result Execution time Memory
748639 2023-05-26T16:37:28 Z Alan 버스 (JOI14_bus) C++17
85 / 100
 322 ms 34380 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) {
		mn[r] = y;
		function<void (int)> dfs = [&] (int u) {
			auto it = G[u].lower_bound({0, mn[u], 0});
			for (; 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 5032 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 4 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 4 ms 5204 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 4 ms 5092 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 22 ms 6684 KB Output is correct
3 Correct 27 ms 6604 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 5 ms 5140 KB Output is correct
6 Incorrect 5 ms 5036 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 217 ms 32820 KB Output is correct
2 Correct 213 ms 32716 KB Output is correct
3 Correct 210 ms 32744 KB Output is correct
4 Correct 212 ms 32696 KB Output is correct
5 Correct 224 ms 32820 KB Output is correct
6 Correct 227 ms 32588 KB Output is correct
7 Correct 251 ms 31748 KB Output is correct
8 Correct 205 ms 31200 KB Output is correct
9 Correct 216 ms 32652 KB Output is correct
10 Correct 289 ms 31076 KB Output is correct
11 Correct 250 ms 31208 KB Output is correct
12 Correct 273 ms 31180 KB Output is correct
13 Correct 262 ms 31196 KB Output is correct
14 Correct 284 ms 31200 KB Output is correct
15 Correct 322 ms 31156 KB Output is correct
16 Correct 65 ms 23348 KB Output is correct
17 Correct 61 ms 23416 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 34296 KB Output is correct
2 Correct 233 ms 33960 KB Output is correct
3 Correct 240 ms 34380 KB Output is correct
4 Correct 257 ms 34380 KB Output is correct
5 Correct 245 ms 33988 KB Output is correct
6 Correct 228 ms 33956 KB Output is correct
7 Correct 290 ms 33360 KB Output is correct
8 Correct 232 ms 34108 KB Output is correct
9 Correct 243 ms 34360 KB Output is correct
10 Correct 295 ms 32832 KB Output is correct
11 Correct 320 ms 32784 KB Output is correct
12 Correct 301 ms 32788 KB Output is correct
13 Correct 283 ms 32876 KB Output is correct
14 Correct 284 ms 32716 KB Output is correct
15 Correct 273 ms 32780 KB Output is correct
16 Correct 83 ms 24348 KB Output is correct