Submission #42317

#	Time	Username	Problem	Language	Result	Execution time	Memory
42317		minkank	버스 (JOI14_bus)	C++14	100 / 100	383 ms	51864 KiB

bus

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 3e5 + 5;

typedef pair<int, int> ii;
#define x first
#define y second

struct data {
	int u, v, x, y, id;
} qu[N + M];

int n, m, q, f[N], ans[N];
set<ii> e[N];

void dfs(int u, int lim) {
	while(e[u].size() && qu[(*e[u].begin()).y].y <= lim) {
		int id = (*e[u].begin()).y; e[u].erase(e[u].begin());
		f[qu[id].u] = max(f[qu[id].u], qu[id].x);
		dfs(qu[id].u, f[qu[id].u]);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) cin >> qu[i].u >> qu[i].v >> qu[i].x >> qu[i].y;
	cin >> q;
	for(int i = 1; i <= q; ++i) cin >> qu[i + m].y, qu[i + m].id = i;
	sort(qu + 1, qu + m + q + 1, [](data a, data b) { return a.y < b.y || (a.y == b.y && a.id < b.id); });
	f[n] = 1e9; for(int i = 1; i < n; ++i) f[i] = -1;
	for(int i = 1; i <= m + q + 1; ++i) {
		if(qu[i].id) ans[qu[i].id] = f[1];
		else {
			e[qu[i].v].insert(ii(qu[i].y, i));
			dfs(qu[i].v, f[qu[i].v]);
		}
	}
	for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50