제출 #807149

#제출 시각아이디문제언어결과실행 시간메모리
807149anhduc2701Travelling Merchant (CCO21_day2problem1)C++17
0 / 25
119 ms38360 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define eb emplace_back #define PI acos(-1.0) #define fi first #define se second #define mp make_pair #define pb push_back #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define BIT(x, i) (1 & ((x) >> (i))) #define MASK(x) (1LL << (x)) #define task "tnc" #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) typedef long long ll; typedef long double ld; const ll INF = 1e18; const int maxn = 1e6 + 5; const int mod = 1e9 + 7; const int mo = 998244353; using pi = pair<ll, ll>; using vi = vector<ll>; using pii = pair<pair<ll, ll>, ll>; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int n, m; struct Edge { int a, b, r, p; bool operator<(const Edge &x) { return r < x.r; } } ind[maxn]; vector<int> G[maxn]; int deg[maxn]; int ans[maxn]; bool ok[maxn]; signed main() { cin.tie(0), cout.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> ind[i].a >> ind[i].b >> ind[i].r >> ind[i].p; } sort(ind + 1, ind + 1 + m); for (int i = 1; i <= m; i++) { G[ind[i].b].pb(i); deg[ind[i].a]++; } queue<int> qu; for (int i = 1; i <= n; i++) { ans[i] = -2; if (deg[i] == 0) { qu.push(i); } } while (qu.size()) { int u = qu.front(); qu.pop(); ans[u] = -1; for (auto v : G[u]) { deg[ind[v].a]--; ok[v] = 1; if (deg[ind[v].a] == 0) { qu.push(ind[v].a); } } } for (int i = m; i >= 1; i--) { if (ok[i] == 0) { deg[ind[i].a]--; if (deg[ind[i].a] == 0) { qu.push(ind[i].a); while (qu.size()) { int u = qu.front(); ans[u] = ind[i].r; qu.pop(); for (auto v : G[u]) { deg[ind[v].a]--; ok[v] = 1; if (ans[ind[v].a] == -2) { ans[ind[v].a] = max(ans[ind[v].b] - ind[v].p, ind[v].r); // cout << ans[ind[v].b] << " " << ind[v].b << "\n"; } else { ans[ind[v].a] = min(ans[ind[v].a], max(ans[ind[v].b] - ind[v].p, ind[v].r)); } if (deg[ind[v].a] == 0) { qu.push(ind[v].a); } } } } } } for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...