Submission #614132

#TimeUsernameProblemLanguageResultExecution timeMemory
614132PiejanVDCShortcut (IOI16_shortcut)C++17
0 / 100
2 ms2688 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; const int mxN = (int)1e5+5; int a=-1,b=-1; long long C; bool ok; vector<pair<int,long long>>adj[mxN]; pair<long long, int>search_(int u, int e = -1) { //cout << u << ' '; pair<long long, int>curr = {0, u}; for(auto z : adj[u]) if(z.first != e && (ok || !((a == u && b == z.first && z.second == C) || (a == z.first && b == u && z.second == C)))) { auto X = search_(z.first, u); X.first += z.second; curr = max(curr, X); } return curr; } long long dfs(int u, int e = -1) { long long d = 0; for(auto z : adj[u]) if(z.first != e && (ok || !((a == u && b == z.first && z.second == C) || (a == z.first && b == u && z.second == C)))) { d = max(d, z.second + dfs(z.first, u)); } return d; } long long solve() { return dfs(search_(0).second); } long long find_shortcut(int n, vector<int>l, vector<int>d, int c) { for(int i = 0 ; i < n-1 ; i++) adj[i].push_back({i+1, l[i]}), adj[i+1].push_back({i, l[i]}), adj[i].push_back({n+i,d[i]}), adj[n+i].push_back({i,d[i]}); adj[n-1].push_back({n+n-1,d[n-1]}); adj[n+n-1].push_back({n-1,d[n-1]}); long long ans = solve(); for(int i = 0 ; i < n ; i++) { for(int j = i+1 ; j < n ; j++) { if(i+1==j&&l[i]==c)ok=1; adj[i].push_back({j, c}); adj[j].push_back({i, c}); a = i, b = i+1, C = l[a]; long long mx = solve(); a = j-1, b = j, C = l[j-1]; mx = max(mx, solve()); adj[i].pop_back(); adj[j].pop_back(); ans = min(ans, mx); //cout << i << ' ' << j << ' ' << ans << '\n'; ok=0; } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...