Submission #930584

#TimeUsernameProblemLanguageResultExecution timeMemory
930584AtabayRajabliRace (IOI11_race)C++17
0 / 100
1 ms2396 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define pb push_back const int sz = 1e3 + 5; int t; int dp[15][sz], in[sz], out[sz], d[sz], e[sz]; vector<array<int, 2>> g[sz]; void dfs(int v, int p) { dp[0][v] = p; in[v] = ++t; for(auto i : g[v]) { if(i[0] == p)continue; d[i[0]] = d[v] + i[1]; e[i[0]] = e[v] + 1; dfs(i[0], v); } out[v] = ++t; } bool anc(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int lca(int u, int v) { if(anc(u, v))return u; if(anc(v, u))return v; for(int i = 10; i >= 0; i--) { if(anc(dp[i][v], u))continue; v = dp[i][v]; } return dp[0][v]; } int dist(int u, int v) { return d[u] + d[v] - d[lca(u, v)] * 2; } int len(int u, int v) { return e[u] + e[v] - e[lca(u, v)] * 2; } int best_path(int n, int k, int h[][2], int l[]) { for(int i = 0; i < n; i++) { int u = ++h[i][0], v = ++h[i][1], w = l[i]; g[u].pb({v, w}); g[v].pb({u, w}); } dfs(1, 0); for(int i = 1; i < 11; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } int mn = 1e9 + 10; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { if(dist(i, j) != k)continue; mn = min(mn, len(i, j)); } } return mn; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...