Submission #1244862

#TimeUsernameProblemLanguageResultExecution timeMemory
1244862tvgk버스 (JOI14_bus)C++20
100 / 100
131 ms30788 KiB
#include<bits/stdc++.h> using namespace std; #define task "a" #define se second #define fi first #define ll long long #define ii pair<ll, ll> const long mxN = 3e5 + 7, inf = 1e9 + 7; int n, m, v[mxN], en[mxN], vis[mxN], ctr[mxN], mn[mxN]; vector<int> val[mxN]; vector<ii> w[mxN]; bool cmp(ii u, ii v) { return u.fi < v.fi; } int DFS(int j, int t) { if (j == n) return t; if (!vis[j]) { mn[j] = inf; val[j].resize(w[j].size()); sort(w[j].begin(), w[j].end(), cmp); ctr[j] = w[j].size() - 1; vis[j] = 1; } while (ctr[j] >= 0 && w[j][ctr[j]].fi >= t) { int id = w[j][ctr[j]].se; mn[j] = min(mn[j], DFS(v[id], en[id])); val[j][ctr[j]] = mn[j]; ctr[j]--; } int tmp = lower_bound(w[j].begin(), w[j].end(), ii(t, 0)) - w[j].begin(); if (tmp >= w[j].size()) return inf; return val[j][tmp]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen(task".INP", "r", stdin); // freopen(task".OUT", "w", stdout); cin >> n >> m; for (int i = 1; i <= m; i++) { int stt, u; cin >> u >> v[i] >> stt >> en[i]; w[u].push_back({stt, i}); } DFS(1, 0); int q; cin >> q; for (int i = 1; i <= q; i++) { int tmp; cin >> tmp; tmp = upper_bound(val[1].begin(), val[1].end(), tmp) - val[1].begin() - 1; if (tmp < 0) cout << -1 << '\n'; else cout << w[1][tmp].fi << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...