Submission #748639

#	Time	Username	Problem	Language	Result	Execution time	Memory
748639		Alan	버스 (JOI14_bus)	C++17	85 / 100	322 ms	34380 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 () {
	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 / 20
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50