Submission #1025917

#TimeUsernameProblemLanguageResultExecution timeMemory
1025917onbertDreaming (IOI13_dreaming)C++17
47 / 100
55 ms14796 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5, INF = 1e9; int n, m, l; vector<pair<int,int>> adj[maxn]; int dist[maxn]; vector<int> cur; void dfs(int u) { cur.push_back(u); for (auto [v, w]:adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + w; dfs(v); } } int finish; vector<int> track; bool done; void dfs2(int u) { if (!done) track.push_back(u); if (u==finish) done = true; for (auto [v, w]:adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + w; dfs2(v); } if (!done) track.pop_back(); } int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) { n = N, m = M, l = L; for (int i=0;i<m;i++) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } for (int i=0;i<n;i++) dist[i] = -1; int32_t ans1 = l, ans2 = 0; for (int i=0;i<n;i++) if (dist[i] == -1) { cur.clear(); dist[i] = 0; dfs(i); int start = i; for (int j:cur) if (dist[j] > dist[start]) start = j; for (int j:cur) dist[j] = -1; cur.clear(); dist[start] = 0; dfs(start); finish = start; for (int j:cur) if (dist[j] > dist[finish]) finish = j; ans2 = max(dist[finish], ans2); for (int j:cur) dist[j] = -1; dist[start] = 0, done = false; track.clear(); dfs2(start); int cost = INF; for (int j:track) cost = min(max(dist[finish]-dist[j], dist[j]), cost); ans1 += cost; } return max(ans1, ans2); } // signed main() { // ios::sync_with_stdio(0); cin.tie(0); // int32_t n, m, l; // cin >> n >> m >> l; // int32_t a[m], b[m], t[m]; // for (int i=0;i<m;i++) cin >> a[i] >> b[i] >> t[i]; // cout << travelTime(n, m, l, a, b, t) << endl; // }
#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...