| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 42317 |
2018-02-26T01:28:32 Z |
minkank |
버스 (JOI14_bus) |
C++14 |
|
383 ms |
51864 KB |
#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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5184 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5272 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5416 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5416 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5416 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5416 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5416 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5416 KB |
Output is correct |
| 11 |
Correct |
6 ms |
5532 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5584 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5760 KB |
Output is correct |
| 14 |
Correct |
7 ms |
5760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5760 KB |
Output is correct |
| 2 |
Correct |
40 ms |
9608 KB |
Output is correct |
| 3 |
Correct |
40 ms |
10396 KB |
Output is correct |
| 4 |
Correct |
9 ms |
10396 KB |
Output is correct |
| 5 |
Correct |
8 ms |
10396 KB |
Output is correct |
| 6 |
Correct |
10 ms |
10396 KB |
Output is correct |
| 7 |
Correct |
34 ms |
10520 KB |
Output is correct |
| 8 |
Correct |
6 ms |
10520 KB |
Output is correct |
| 9 |
Correct |
37 ms |
11064 KB |
Output is correct |
| 10 |
Correct |
62 ms |
12404 KB |
Output is correct |
| 11 |
Correct |
37 ms |
12572 KB |
Output is correct |
| 12 |
Correct |
39 ms |
13980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
307 ms |
39664 KB |
Output is correct |
| 2 |
Correct |
308 ms |
48404 KB |
Output is correct |
| 3 |
Correct |
276 ms |
48708 KB |
Output is correct |
| 4 |
Correct |
282 ms |
48708 KB |
Output is correct |
| 5 |
Correct |
304 ms |
48912 KB |
Output is correct |
| 6 |
Correct |
298 ms |
48912 KB |
Output is correct |
| 7 |
Correct |
292 ms |
48912 KB |
Output is correct |
| 8 |
Correct |
272 ms |
48912 KB |
Output is correct |
| 9 |
Correct |
284 ms |
48912 KB |
Output is correct |
| 10 |
Correct |
263 ms |
48912 KB |
Output is correct |
| 11 |
Correct |
297 ms |
48912 KB |
Output is correct |
| 12 |
Correct |
263 ms |
48912 KB |
Output is correct |
| 13 |
Correct |
290 ms |
48912 KB |
Output is correct |
| 14 |
Correct |
282 ms |
48912 KB |
Output is correct |
| 15 |
Correct |
277 ms |
48912 KB |
Output is correct |
| 16 |
Correct |
90 ms |
48912 KB |
Output is correct |
| 17 |
Correct |
85 ms |
48912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
338 ms |
51864 KB |
Output is correct |
| 2 |
Correct |
383 ms |
51864 KB |
Output is correct |
| 3 |
Correct |
338 ms |
51864 KB |
Output is correct |
| 4 |
Correct |
353 ms |
51864 KB |
Output is correct |
| 5 |
Correct |
333 ms |
51864 KB |
Output is correct |
| 6 |
Correct |
345 ms |
51864 KB |
Output is correct |
| 7 |
Correct |
341 ms |
51864 KB |
Output is correct |
| 8 |
Correct |
357 ms |
51864 KB |
Output is correct |
| 9 |
Correct |
359 ms |
51864 KB |
Output is correct |
| 10 |
Correct |
326 ms |
51864 KB |
Output is correct |
| 11 |
Correct |
346 ms |
51864 KB |
Output is correct |
| 12 |
Correct |
323 ms |
51864 KB |
Output is correct |
| 13 |
Correct |
321 ms |
51864 KB |
Output is correct |
| 14 |
Correct |
310 ms |
51864 KB |
Output is correct |
| 15 |
Correct |
331 ms |
51864 KB |
Output is correct |
| 16 |
Correct |
129 ms |
51864 KB |
Output is correct |
