oj.uz

Submission #748621

# Submission time Handle Problem Language Result Execution time Memory
748621 2023-05-26T15:24:53 Z Alan 버스 (JOI14_bus) C++17
0 / 100
 1000 ms 34492 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 () {
	vector<pair<int, int>> ans;
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, s, t;
		cin >> u >> v >> s >> t;
		G[u].insert({v, s, t});
	}
	for (int i = 1; i <= n; i++) mn[i] = inf;
	for (auto [r, x, y] : G[1]) {
		priority_queue<edge> pq;
		vector<vector<int>> del;
		pq.push({r, y, 0});
		mn[r] = y;
		while (!pq.empty()) {
			auto [u, w, z] = pq.top();
			pq.pop();
			if (mn[u] != w) continue;
			for (auto [v, s, t] : G[u]) if (mn[u] <= s && t < mn[v]) {
				mn[v] = t;
				pq.push({v, t, 0});
				del.push_back({u, v, s, t});
			}
		}
		for (auto& u : del) G[u[0]].erase({u[1], u[2], u[3]});
		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 Correct 5 ms 4948 KB Output is correct
2 Correct 4 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5016 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5020 KB Output is correct
2 Correct 166 ms 6748 KB Output is correct
3 Correct 183 ms 6528 KB Output is correct
4 Correct 20 ms 5208 KB Output is correct
5 Correct 20 ms 5168 KB Output is correct
6 Incorrect 17 ms 5080 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 32772 KB Output is correct
2 Correct 483 ms 32848 KB Output is correct
3 Correct 477 ms 32912 KB Output is correct
4 Correct 492 ms 32744 KB Output is correct
5 Correct 500 ms 32860 KB Output is correct
6 Correct 491 ms 32768 KB Output is correct
7 Correct 646 ms 31904 KB Output is correct
8 Correct 508 ms 32772 KB Output is correct
9 Correct 486 ms 32824 KB Output is correct
10 Execution timed out 1053 ms 31220 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 34304 KB Output is correct
2 Correct 648 ms 33944 KB Output is correct
3 Correct 658 ms 34348 KB Output is correct
4 Correct 649 ms 34492 KB Output is correct
5 Correct 674 ms 34004 KB Output is correct
6 Correct 701 ms 34128 KB Output is correct
7 Correct 703 ms 33444 KB Output is correct
8 Correct 651 ms 34236 KB Output is correct
9 Correct 646 ms 34332 KB Output is correct
10 Execution timed out 1083 ms 32088 KB Time limit exceeded
11 Halted 0 ms 0 KB -