제출 #801743

#제출 시각아이디문제언어결과실행 시간메모리
801743SanguineChameleonTravelling Merchant (CCO21_day2problem1)C++17
0 / 25
2079 ms25628 KiB
#include <bits/stdc++.h> using namespace std; void just_do_it(); int main() { #ifdef KAMIRULEZ freopen("kamirulez.inp", "r", stdin); freopen("kamirulez.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); just_do_it(); return 0; } struct edge { int v, a, b; edge(int _v, int _a, int _b): v(_v), a(_a), b(_b) {}; }; const int maxn = 2e5 + 20; const int inf = 1e9 + 20; vector<edge> adj[maxn]; int lt[maxn]; int rt[maxn]; bool flag[maxn]; bool dfs(int u, int x) { if (x < lt[u]) { return false; } if (x > rt[u]) { return true; } flag[u] = true; for (auto e: adj[u]) { if (x >= e.a) { if (flag[e.v] || dfs(e.v, min(inf, x + e.b))) { flag[u] = false; rt[u] = min(x, inf); return true; } } } flag[u] = false; lt[u] = x + 1; return false; } void just_do_it() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, a, b; cin >> u >> v >> a >> b; adj[u].emplace_back(v, a, b); } for (int i = 1; i <= n; i++) { lt[i] = 0; rt[i] = inf; } for (int i = 1; i <= n; i++) { int lt = 1; int rt = inf; int res = -1; while (lt <= rt) { int mt = (lt + rt) / 2; if (dfs(i, mt)) { res = mt; rt = mt - 1; } else { lt = mt + 1; } } cout << res << " "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...