Submission #1233138

#TimeUsernameProblemLanguageResultExecution timeMemory
123313812baaterDreaming (IOI13_dreaming)C++20
0 / 100
28 ms12096 KiB
#include "dreaming.h" #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100100; int longest[MAXN]; int longestChild[MAXN]; int secondLongest[MAXN]; int secondLongestChild[MAXN]; bool visited[MAXN]; vector<pair<int,int>> ADJ[MAXN]; int dfs(int node, int parent) { visited[node] = true; for (auto [child, w] : ADJ[node]) { if (child == parent) continue; int ln = dfs(child, node) + w; if (ln > secondLongest[node]) { secondLongest[node] = ln; secondLongestChild[node] = child; if (secondLongest[node] > longest[node]) { swap(secondLongest[node], longest[node]); swap(secondLongestChild[node], longestChild[node]); } } } return longest[node]; } int min_max_dfs(int node, int parent, int other) { if (ADJ[node].size() == 0) return 0; int best = 2000000000; for (auto [child, w] : ADJ[node]) { if (child == parent) continue; if (child != longestChild[node]) { best = min(best, min_max_dfs(child, node, max(other,longest[node]) + w)); } else { best = min(best, min_max_dfs(child, node, max(other, secondLongest[node]) + w)); } } // cout << "\n" << node << " " << other << " " << longest[node] << "\n\n"; return min(best, max(other,longest[node])); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; i++) { ADJ[A[i]].emplace_back(B[i],T[i]); ADJ[B[i]].emplace_back(A[i],T[i]); } for (int i = 0; i < N; i++) { longestChild[i] = -1; } priority_queue<int> pq; pq.push(0); pq.push(0); for (int i = 0; i < N; i++) { if (visited[i]) continue; dfs(i, i); int num = min_max_dfs(i,i,0); pq.push(num); // cout << i << " " << num << "\n"; // cout << longest[i] << " " << secondLongest[i] << "\n"; } if (M == N-1) { return pq.top(); } int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); return a+b+L; }
#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...