Submission #865995

#TimeUsernameProblemLanguageResultExecution timeMemory
865995Onur_IlgazDreaming (IOI13_dreaming)C++17
100 / 100
57 ms16788 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; vector <vector<pair<int, int> > > adj; vector <int> mxdepth; bitset <100000> vis; int mxDia; void dfs(int node, int ata = -1) { vis[node] = 1; int arr[3] = {0}; for(auto &[to, w]:adj[node]) { if(to == ata) continue; dfs(to, node); mxdepth[node] = max(mxdepth[node], mxdepth[to] + w); arr[2] = mxdepth[to] + w; for(int i = 1; ~i; i--) { if(arr[i] < arr[i + 1]) { swap(arr[i], arr[i + 1]); } } } mxDia = max(arr[0] + arr[1], mxDia); } int dfs2(int node, int ust = 0, int ata = -1) { // cout<<"node: "<<node<<" "<<ust<<"\n"; int arr[3] = {0, 0, 0}, brr[3] = {-1, -1, -1}; for(auto &[to, w]:adj[node]) { if(to == ata) continue; arr[2] = mxdepth[to] + w; brr[2] = to; for(int i = 1; ~i; i--) { if(arr[i] < arr[i + 1]) { swap(arr[i], arr[i + 1]); swap(brr[i], brr[i + 1]); } } } for(auto &[to, w]:adj[node]) { if(to == ata) continue; int othermax = to == brr[0] ? arr[1] : arr[0]; int ifgoust = max(ust + w, othermax + w); int valifto = max(mxdepth[to], ifgoust); // cout<<arr[0]<<" "<<arr[1]<<"\n"; // cout<<brr[0]<<" "<<brr[1]<<"\n"; // cout<<to<<" "<<othermax<<" "<<ifgoust<<" "<<valifto<<"\n"; if(max(ust, mxdepth[node]) > valifto) { return dfs2(to, ifgoust, node); } } return max(ust, mxdepth[node]); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { adj.assign(N, vector <pair<int, int> > (0)); mxdepth.assign(N, 0); for(int i = 0; i < M; i++) { int a = A[i], b = B[i], t = T[i]; adj[a].push_back({b, t}); adj[b].push_back({a, t}); } vector <int> trees; for(int i = 0; i < N; i++) { if(!vis[i]) { dfs(i); int depth = dfs2(i); trees.push_back(depth); // cout<<"\n"; } } if(trees.size() == 1) { return mxDia; } sort(trees.begin(), trees.end()); reverse(trees.begin(), trees.end()); int ans = max(mxDia, trees[0] + trees[1] + L); // cout<<trees[0]<<" "<<trees[1]<<"\n"; if(trees.size() > 2) { ans = max(ans, trees[1] + trees[2] + 2 * L); } return ans; }
#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...