답안 #748642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748642 2023-05-26T16:50:19 Z Alan 버스 (JOI14_bus) C++17
0 / 100
258 ms 24932 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.t > b.t;});
	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});
			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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 23 ms 5784 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 24092 KB Output is correct
2 Correct 209 ms 24152 KB Output is correct
3 Correct 220 ms 24208 KB Output is correct
4 Correct 211 ms 24116 KB Output is correct
5 Correct 218 ms 24264 KB Output is correct
6 Correct 225 ms 23948 KB Output is correct
7 Incorrect 258 ms 23628 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 24732 KB Output is correct
2 Correct 227 ms 24364 KB Output is correct
3 Correct 227 ms 24800 KB Output is correct
4 Correct 253 ms 24932 KB Output is correct
5 Correct 216 ms 24416 KB Output is correct
6 Incorrect 223 ms 24584 KB Output isn't correct
7 Halted 0 ms 0 KB -