Submission #1014214

#TimeUsernameProblemLanguageResultExecution timeMemory
1014214gmroh06Telegraph (JOI16_telegraph)C++17
0 / 100
0 ms348 KiB
#import <bits/stdc++.h> using namespace std; using ll = long long; inline void init() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } int main() { init(); ll n, ans = 0; cin >> n; vector<pair<ll, ll>> gr(n + 1); vector<ll> vst(n + 1), x(n + 1), y(n + 1); vector<bool> cycle(n + 1); for (ll i = 1; i <= n; i++) { cin >> gr[i].first >> gr[i].second; ans += gr[i].second; } for (ll i = 1, cnt = 0;; i = gr[i].first, vst[++cnt] = 1) { if (vst[i]) { if (i == 1 and cnt == n) { cout << 0; return 0; } break; } } fill(vst.begin(), vst.end(), 0); for (ll i = 1, tmp = 1; i <= n; tmp = ++i) { if (vst[i]) continue; while (!vst[tmp]) { vst[tmp] = i; tmp = gr[tmp].first; } if (vst[tmp] != i) continue; while (!cycle[tmp]) { cycle[tmp] = true; tmp = gr[tmp].first; } } for (ll i = 1; i <= n; i++) { x[gr[i].first] = max(x[gr[i].first], gr[i].second); if (!cycle[i]) y[gr[i].first] = max(y[gr[i].first], gr[i].second); } for (ll i = 1, mx, tmp = 1; i <= n; tmp = ++i) { ans -= x[i]; if (!cycle[i]) continue; mx = -1e18; while (cycle[tmp]) { mx = max(mx, y[tmp] - x[tmp]); cycle[tmp] = false; tmp = gr[tmp].first; } ans -= mx; } cout << ans; return 0; }

Compilation message (stderr)

telegraph.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
    1 | #import <bits/stdc++.h>
      |  ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...