Submission #967229

#TimeUsernameProblemLanguageResultExecution timeMemory
967229VMaksimoski008Dreaming (IOI13_dreaming)C++14
100 / 100
60 ms15816 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; const int maxn = 1e5 + 5; int n, m, l; ll val, mx, D; vector<pii> graph[maxn]; vector<bool> vis(maxn); vector<ll> dist(maxn), dist2(maxn); vector<int> seen; void dfs(int u, int p, bool t) { vis[u] = 1; if(dist[u] > val) val = dist[u], mx = u; if(t) seen.push_back(u); D = max(D, dist[u]); for(auto &[v, w] : graph[u]) { if(v == p) continue; dist[v] = dist[u] + w; dfs(v, u, t); } } void dfs2(int u, int p) { for(auto &[v, w] : graph[u]) { if(v == p) continue; dist2[v] = dist2[u] + w; dfs2(v, u); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N, m = M, l = L; ll ans = 0; for(int i=0; i<m; i++) { graph[A[i]].push_back({ B[i], T[i] }); graph[B[i]].push_back({ A[i], T[i] }); } vector<pair<ll, int> > v; for(int i=0; i<n; i++) { if(vis[i]) continue; seen.clear(); mx=i, val=0; dfs(i, i, 0); D = 0; dist[mx] = 0; dfs(mx, mx, 1); int U = mx, V = U; for(int &x : seen) if(dist[x] > dist[V]) V = x; dfs2(V, V); ll val=1e18, curr=0; for(int &x : seen) { if(max(dist[x], dist2[x]) < val) { val = max(dist[x], dist2[x]); curr = x; } } v.push_back({ val, curr }); ans = max(ans, D); } sort(v.begin(), v.end()); reverse(v.begin(), v.end()); if(v.size() > 1) { ans = max(ans, v[0].first + v[1].first + l); if(v.size() > 2) ans = max(ans, v[1].first + v[2].first + 2 * l); } return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, bool)':
dreaming.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto &[v, w] : graph[u]) {
      |               ^
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto &[v, w] : graph[u]) {
      |               ^
#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...