# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
42363 |
2018-02-26T13:46:33 Z |
nickyrio |
버스 (JOI14_bus) |
C++14 |
|
267 ms |
35244 KB |
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
using namespace std;
struct edge {
int a, b, x, y;
}g[N];
vector<int> e[N];
int d[N], visited[N];
int n, m;
void Enter() {
IO;
cin >> n >> m;
REP(i, m) {
cin >> g[i].a >> g[i].b >> g[i].x >> g[i].y;
e[g[i].a].push_back(i);
}
}
bool disabled[N];
void dfs(int u, int isEdge, int MAX, int now) {
if (isEdge) {
visited[u] = true;
d[u] = MAX;
if (!disabled[g[u].b]) dfs(g[u].b, 0, MAX, now);
}
else {
bool stop = true;
for (int id : e[u]) {
if (visited[id] == false && g[id].x >= now) {
dfs(id, 1, MAX, g[id].y);
stop = false;
}
}
if (stop) disabled[u] = true;
}
}
vector<pp> res;
void Process() {
sort(e[1].begin(), e[1].end(), [] (const int &a, const int &b) {
return g[a].x > g[b].x;
});
for (int id : e[1]) {
if (visited[id] == false) {
dfs(id, 1, g[id].x, g[id].y);
}
}
REP(i, m) {
if (g[i].b == n && visited[i]) {
res.push_back(pp(g[i].y, d[i]));
}
}
sort(res.begin(), res.end());
REP(i, res.size()) if (i) {
res[i].second = max(res[i].second, res[i - 1].second);
}
}
void Query() {
int q;
cin >> q;
REP(i, q) {
int x;
cin >> x;
int pos = upper_bound(res.begin(), res.end(), pp(x + 1, -1)) - res.begin() - 1;
if (pos < 0) cout << -1 << '\n';
else cout << res[pos].second << '\n';
}
}
int main() {
Enter();
Process();
Query();
}
Compilation message
bus.cpp: In function 'void Process()':
bus.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i, a) for (int i = 0; i<a; ++i)
^
bus.cpp:69:5: note: in expansion of macro 'REP'
REP(i, res.size()) if (i) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
20 ms |
24032 KB |
Output is correct |
3 |
Correct |
20 ms |
24032 KB |
Output is correct |
4 |
Correct |
23 ms |
24032 KB |
Output is correct |
5 |
Correct |
20 ms |
24036 KB |
Output is correct |
6 |
Correct |
20 ms |
24052 KB |
Output is correct |
7 |
Incorrect |
20 ms |
24056 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
24112 KB |
Output is correct |
2 |
Correct |
43 ms |
24924 KB |
Output is correct |
3 |
Correct |
43 ms |
24924 KB |
Output is correct |
4 |
Correct |
23 ms |
24924 KB |
Output is correct |
5 |
Incorrect |
22 ms |
24924 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
34292 KB |
Output is correct |
2 |
Correct |
198 ms |
34292 KB |
Output is correct |
3 |
Correct |
204 ms |
34292 KB |
Output is correct |
4 |
Correct |
205 ms |
34320 KB |
Output is correct |
5 |
Correct |
193 ms |
34320 KB |
Output is correct |
6 |
Correct |
209 ms |
34832 KB |
Output is correct |
7 |
Incorrect |
180 ms |
34832 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
267 ms |
34964 KB |
Output is correct |
2 |
Correct |
224 ms |
34964 KB |
Output is correct |
3 |
Correct |
226 ms |
35072 KB |
Output is correct |
4 |
Correct |
238 ms |
35072 KB |
Output is correct |
5 |
Correct |
257 ms |
35072 KB |
Output is correct |
6 |
Correct |
223 ms |
35244 KB |
Output is correct |
7 |
Incorrect |
220 ms |
35244 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |