Submission #288296

#TimeUsernameProblemLanguageResultExecution timeMemory
288296BeanZDreaming (IOI13_dreaming)C++14
77 / 100
1083 ms12408 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; #define ll int #define endl '\n' const int N = 1e5 + 5; ll dp[N], res, vis[N], lg, cur; vector<pair<ll, ll>> node[N]; void dfsFirst(ll u){ vis[u] = 1; for (auto j : node[u]){ if (vis[j.first]) continue; dfsFirst(j.first); dp[u] = max(dp[u], dp[j.first] + j.second); } } void reroot(ll u, ll v){ dp[u] = 0; for (auto j : node[u]){ if (j.first == v) continue; dp[u] = max(dp[u], dp[j.first] + j.second); } dp[v] = 0; for (auto j : node[v]){ dp[v] = max(dp[v], dp[j.first] + j.second); } res = min(res, dp[v]); } void dfs(ll u, ll p){ for (auto j : node[u]){ if (j.first == p) continue; reroot(u, j.first); dfs(j.first, u); reroot(j.first, u); } } void FindFirstNode(ll u, ll p, ll dist){ if (dist > lg){ lg = dist; cur = u; } for (auto j : node[u]){ if (j.first == p) continue; FindFirstNode(j.first, u, dist + j.second); } } void FindDia(ll u, ll p, ll dist){ if (dist > lg){ lg = dist; } for (auto j : node[u]){ if (j.first == p) continue; FindDia(j.first, u, dist + j.second); } } int travelTime(int N, int M, int L, int A[],int B[],int T[]){ for (int i = 1; i <= M; i++){ node[A[i - 1] + 1].push_back({B[i - 1] + 1, T[i - 1]}); node[B[i - 1] + 1].push_back({A[i - 1] + 1, T[i - 1]}); } vector<ll> pq; ll ans = 0; for (int i = 1; i <= N; i++){ if (!vis[i]){ dfsFirst(i); res = dp[i]; dfs(i, i); lg = -1; FindFirstNode(i, i, 0); lg = -1; FindDia(cur, cur, 0); ans = max(ans, lg); pq.push_back(res); } } sort(pq.begin(), pq.end(), greater<ll>()); if (pq.size() == 1) return ans; if (pq.size() == 2) return max(ans, pq[0] + pq[1] + L); return max(max(pq[1] + pq[2] + 2 * L, pq[0] + pq[1] + L), ans); } /* int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("VietCT.INP", "r")){ freopen("VietCT.INP", "r", stdin); freopen("VietCT.OUT", "w", stdout); } int n, m, l; cin >> n >> m >> l; vector<int> a, b, t; for (int i = 1; i <= m; i++){ int u, v, c; cin >> u >> v >> c; a.push_back(u + 1); b.push_back(v + 1); t.push_back(c); } cout << travelTime(n, m, l, a, b, t); } /* 6 2 1000 0 1 10 2 3 10 */

Compilation message (stderr)

dreaming.cpp:103:1: warning: "/*" within comment [-Wcomment]
  103 | /*
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...