Submission #341946

#TimeUsernameProblemLanguageResultExecution timeMemory
341946ijxjdjdDreaming (IOI13_dreaming)C++14
0 / 100
51 ms13804 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int MAXN = (int)(1e5)+5; vector<pair<int, int>> adj[MAXN]; int cur = -1; int curI = -1; pair<int, int> best; bool visited[MAXN]; pair<int, int> sep = {(int)(1e9), (int)(1e9)}; int mx = 0; void furthest(int n, int p, int d) { visited[n] = true; if (d > cur) { cur = d; curI = n; } for (pair<int, int> e : adj[n]) { if (e.first != p) { furthest(e.first, n, d+e.second); } } } int getBest(int n, int p, int d) { int distTo = (n == curI ? 0 : (int)(1e9)) ; for (pair<int, int> e : adj[n]) { if (e.first != p) { distTo = min(distTo, getBest(e.first, n, d+e.second) + e.second); } } if (max(d, distTo) < best.first) { best = {max(d, distTo), min(d, distTo)}; } return distTo; } void getSplit(int n) { cur = -1; furthest(n, n, 0); cur = -1; int d1 = curI; furthest(d1, d1, 0); best = {(int)(1e9), (int)(1e9)}; getBest(d1, d1, 0); if (n == 0) { sep=best; } else if (best.first < (int)(1e9)){ if (best.first > sep.first) { sep.second = sep.first; sep.first = best.first; } else if (best.first > sep.second) { sep.second = best.first; } mx = max(mx, best.first + best.second); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { if (N == 1) { return 0; } 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++) { if (!visited[i]) { getSplit(i); } } return max(sep.first + sep.second + L, mx); }
#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...