Submission #932239

#TimeUsernameProblemLanguageResultExecution timeMemory
932239hmm789Shortcut (IOI16_shortcut)C++14
0 / 100
103 ms378708 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 ld[n], rd[n], ld2[n], rd2[n]; for(int i = 0; i < n; i++) { ld[i] = 0; ld2[i] = 0; for(int j = 0; j <= i; j++) { ld[i] = max(ld[i], dst(j, i)); ld[i] = max(ld[i], dst(j+n, i)); ld2[i] = max(ld2[i], dst(j, i+n)); ld2[i] = max(ld2[i], dst(j+n, i+n)); } } for(int i = n-1; i >= 0; i--) { rd[i] = 0; rd2[i] = 0; for(int j = n-1; j >= i; j--) { rd[i] = max(rd[i], dst(j, i)); rd[i] = max(rd[i], dst(j+n, i)); rd2[i] = max(rd2[i], dst(j, i+n)); rd2[i] = max(rd2[i], dst(j+n, i+n)); } } 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 < n; k++) { tmp = max(tmp, min(rd2[k], ds2[k+n][i] + c + rd[j])); tmp = max(tmp, min(ld2[k], ds2[k+n][j] + c + ld[i])); } 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...