Submission #932253

#TimeUsernameProblemLanguageResultExecution timeMemory
932253hmm789Shortcut (IOI16_shortcut)C++14
23 / 100
2061 ms382548 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; //#define int long long #define INF 1000000000000000000 #define MOD 1000000007 #define int long long vector<pair<int, int>> adj[2000000]; int dist[2000000], depth[2000000], p[2000000][21]; void dfs(int x, int pa, int d, int dep) { dist[x] = d; depth[x] = dep; p[x][0] = pa; for(int i = 1; i < 21; i++) { if(p[x][i-1] == -1) break; p[x][i] = p[p[x][i-1]][i-1]; } for(auto i : adj[x]) if(i.first != pa) dfs(i.first, x, d+i.second, dep+1); } int lca(int a, int b) { if(depth[a] < depth[b]) swap(a, b); int h = depth[a]-depth[b]; for(int i = 0; i < 21; i++) { if(h&(1<<i)) a = p[a][i]; } if(a == b) return a; for(int i = 20; i >= 0; i--) { if(p[a][i] != p[b][i]) { a = p[a][i]; b = p[b][i]; } } return p[a][0]; } int dst(int x, int y) { return dist[x]+dist[y]-2*dist[lca(x,y)]; } #undef int long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { #define int long long int ans = INF; for(int k = 0; k < n-1; k++) { adj[k].push_back({k+1, l[k]}); adj[k+1].push_back({k, l[k]}); } for(int k = 0; k < n; k++) { adj[k].push_back({k+n, d[k]}); adj[k+n].push_back({k, d[k]}); } memset(p, -1, sizeof(p)); dfs(0, -1, 0, 0); int ds2[2*n][2*n]; for(int i = 0; i < 2*n; i++) for(int j = 0; j < 2*n; j++) ds2[i][j] = dst(i, j); for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { int tmp = 0; for(int k = 0; k < 2*n; k++) { for(int l = 0; l < 2*n; l++) { tmp = max(tmp, min({ds2[k][l], ds2[k][i]+c+ds2[j][l], ds2[k][j]+c+ds2[i][l]})); } } ans = min(ans, tmp); } } return ans; #undef int }
#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...