제출 #1102436

#제출 시각아이디문제언어결과실행 시간메모리
1102436ThanhsTravelling Merchant (CCO21_day2problem1)C++17
25 / 25
115 ms23020 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define int long long #define endl '\n' #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) ((x) * (x)) mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);} const int NM = 2e5 + 5; struct Edge { int u, v, r, p; bool operator<(const Edge& o) { return r < o.r; } }E[NM]; vector<int> g[NM]; int n, m, deg[NM], ans[NM]; bool ok[NM]; void solve() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> E[i].u >> E[i].v >> E[i].r >> E[i].p; sort(E + 1, E + 1 + m); for (int i = 1; i <= m; i++) { g[E[i].v].push_back(i); deg[E[i].u]++; } queue<int> q; for (int i = 1; i <= n; i++) { ans[i] = -2; if (!deg[i]) q.push(i); } while (q.size()) { int u = q.front(); q.pop(); ans[u] = -1; for (int v : g[u]) { deg[E[v].u]--; ok[v] = 1; if (!deg[E[v].u]) q.push(E[v].u); } } for (int i = m; i >= 1; i--) if (!ok[i]) { ok[i] = 1; deg[E[i].u]--; if (ans[E[i].u] == -2) ans[E[i].u] = E[i].r; else setmin(ans[E[i].u], E[i].r); if (!deg[E[i].u]) { q.push(E[i].u); while (q.size()) { int u = q.front(); q.pop(); for (int v : g[u]) if (!ok[v]) { if (ans[E[v].u] == -2) ans[E[v].u] = max(ans[u] - E[v].p, E[v].r); else setmin(ans[E[v].u], max(ans[u] - E[v].p, E[v].r)); deg[E[v].u]--; ok[v] = 1; if (!deg[E[v].u]) q.push(E[v].u); } } } } for (int i = 1; i <= n; i++) cout << ans[i] << ' '; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); if (fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); } int tc = 1; // cin >> tc; while (tc--) solve(); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...