Submission #1243831

#TimeUsernameProblemLanguageResultExecution timeMemory
1243831rayan_bdDreaming (IOI13_dreaming)C++20
0 / 100
29 ms12096 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; const int mxN = 1e5 + 100; const int INF = 1e9; vector<pair<int,int>> adj[mxN]; int down_dp[mxN], up_dp[mxN]; bool vis[mxN]; int cmax = 0; void dfs(int u, int p){ vis[u] = 1; // cout << u << " "; for(auto it : adj[u]){ if(it.first ^ p){ dfs(it.first, u); down_dp[u] = max(down_dp[u], down_dp[it.first] + it.second); } } } void reroot(int u, int p){ pair<int, int> mx1, mx2; mx1.first = mx2.first = mx2.second = -1; for(auto it : adj[u]){ if(it.first ^ p){ if(mx1.first == -1){ mx1.first = it.first; mx1.second = down_dp[it.first] + it.second; }else if(down_dp[it.first] + it.second >= mx1.second){ swap(mx1, mx2); mx1.first = it.first; mx1.second = down_dp[it.first] + it.second; }else if(down_dp[it.first] + it.second > mx2.second){ mx2.first = it.first; mx2.second = down_dp[it.first] + it.second; } } } for(auto it : adj[u]){ if(it.first ^ p){ if(it.first == mx1.first){ if(mx2.first != -1){ up_dp[it.first] = mx2.second + it.second; } }else if(mx1.first != 1){ up_dp[it.first] = mx1.second + it.second; } up_dp[it.first] = max(up_dp[it.first], up_dp[u] + it.second); reroot(it.first, u); } } cmax = min(cmax, max(up_dp[u], down_dp[u])); } int travelTime(int N,int M,int L,int A[],int B[],int T[]){ 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]}); } vector<int> tokens; for(int i = 0; i < N; ++i){ if(!vis[i]){ cmax = INF; // cout << "started visiting:- "; dfs(i, -1); reroot(i, -1); // cout << "ended visiting\n"; tokens.push_back(cmax); // cout << i << " " << cmax << endl; } } sort(tokens.begin(), tokens.end()); // cout << "2 updp : " << up_dp[2] << " downdp: " << down_dp[2] << endl; if(tokens.size() == 1){ return tokens.back(); }else{ return tokens[tokens.size() - 2] + L + tokens.back(); } }
#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...