Submission #748621

#	Time	Username	Problem	Language	Result	Execution time	Memory
748621		Alan	버스 (JOI14_bus)	C++17	0 / 100	1083 ms	34492 KiB

bus

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50