Submission #42362

#TimeUsernameProblemLanguageResultExecution timeMemory
42362nickyrio버스 (JOI14_bus)C++14
35 / 100
1079 ms35244 KiB
#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); } } void dfs(int u, int isEdge, int MAX, int now) { if (isEdge) { visited[u] = true; d[u] = MAX; dfs(g[u].b, 0, MAX, now); } else { for (int id : e[u]) { if (visited[id] == false && g[id].x >= now) { dfs(id, 1, MAX, g[id].y); } } } } 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 (stderr)

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:65:5: note: in expansion of macro 'REP'
     REP(i, res.size()) if (i) {
     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...