# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
911085 | VMaksimoski008 | Valley (BOI19_valley) | C++14 | 386 ms | 38688 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int LOG = 20, maxn = 1e5 + 5;
int n, s, q, e, timer = 0;
vector<vector<pii> > graph;
int store[maxn+1], in[maxn+1], out[maxn+1], depth[maxn+1], up[maxn+1][LOG];
ll dp[maxn+1], dist[maxn+1], mn[maxn+1][LOG];
void dfs(int u, int p) {
in[u] = timer++;
dp[u] = (store[u] ? dist[u] : 1e17);
for(auto &[v, w] : graph[u]) {
if(v == p) continue;
dist[v] = dist[u] + w;
dfs(v, u);
dp[u] = min(dp[u], dp[v]);
}
out[u] = timer;
}
void dfs2(int u, int p) {
for(int i=1; i<LOG; i++) {
up[u][i] = up[ up[u][i-1] ][i-1];
mn[u][i] = min(mn[u][i-1], mn[ up[u][i-1] ][i-1]);
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |