| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147348 | 2019-08-29T06:33:02 Z | georgerapeanu | Valley (BOI19_valley) | C++11 | 271 ms | 37776 KB |
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
FILE *f = stdin;
FILE *g = stdout;
const int NMAX = 1e5;
const int QMAX = 1e5;
const int LGMAX = 16;
const long long inf = (1LL << 60);
int n,s,q,e;
long long dp[LGMAX + 1][NMAX + 5];
int father[LGMAX + 1][NMAX + 5];
vector<pair<int,int> > graph[NMAX + 5];
pair<int,int> edge[NMAX + 5];
int lin[NMAX + 5],sz;
int st[NMAX + 5];
int dr[NMAX + 5];
long long lvl[NMAX + 5];
void dfs(int nod,int tata){
father[0][nod] = tata;
lin[++sz] = nod;
st[nod] = sz;
for(auto it:graph[nod]){
if(it.first == tata){
continue;
}
lvl[it.first] = it.second + lvl[nod];
dfs(it.first,nod);
dp[0][nod] = min(dp[0][nod],dp[0][it.first] + it.second);
}
dr[nod] = sz;
}
int main(){
fscanf(f,"%d %d %d %d",&n,&s,&q,&e);
for(int i = 1;i < n;i++){
int a,b,w;
fscanf(f,"%d %d %d",&a,&b,&w);
graph[a].push_back({b,w});
graph[b].push_back({a,w});
edge[i] = {a,b};
}
for(int i = 1;i <= n;i++){
dp[0][i] = inf;
}
for(int i = 1;i <= s;i++){
int x;
fscanf(f,"%d",&x);
dp[0][x] = 0;
}
dfs(e,0);
for(int i = 1;i <= n;i++){
dp[0][i] -= lvl[i];
}
for(int h = 1;h <= LGMAX;h++){
for(int i = 1;i <= n;i++){
father[h][i] = father[h - 1][father[h - 1][i]];
if(father[h - 1][i] > 0){
dp[h][i] = min(dp[h - 1][i],dp[h - 1][father[h - 1][i]]);
}
}
}
while(q--){
int e,u;
fscanf(f,"%d %d",&e,&u);
e = (lvl[edge[e].first] < lvl[edge[e].second] ? edge[e].second:edge[e].first);
if(st[e] > st[u] || dr[u] > dr[e]){
fprintf(g,"escaped\n");
}
else{
int nod = u;
long long best = inf;
for(int h = LGMAX;h >= 0;h--){
if(father[h][nod] > 0 && st[e] <= st[father[h][nod]] && dr[father[h][nod]] <= dr[e]){
best = min(best,dp[h][nod]);
nod = father[h][nod];
}
}
best = min(best,dp[0][nod]);///because dp is from curr node to father exclusive
best += lvl[u];
if(best >= inf){
fprintf(g,"oo\n");
}
else{
fprintf(g,"%lld\n",best);
}
}
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 2936 KB | Output is correct |
| 2 | Correct | 7 ms | 2936 KB | Output is correct |
| 3 | Correct | 8 ms | 2936 KB | Output is correct |
| 4 | Correct | 7 ms | 2936 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 2936 KB | Output is correct |
| 2 | Correct | 7 ms | 2936 KB | Output is correct |
| 3 | Correct | 8 ms | 2936 KB | Output is correct |
| 4 | Correct | 7 ms | 2936 KB | Output is correct |
| 5 | Correct | 6 ms | 2936 KB | Output is correct |
| 6 | Correct | 6 ms | 3064 KB | Output is correct |
| 7 | Correct | 6 ms | 3064 KB | Output is correct |
| 8 | Correct | 5 ms | 2936 KB | Output is correct |
| 9 | Correct | 5 ms | 2936 KB | Output is correct |
| 10 | Correct | 5 ms | 3064 KB | Output is correct |
| 11 | Correct | 8 ms | 3064 KB | Output is correct |
| 12 | Correct | 5 ms | 2936 KB | Output is correct |
| 13 | Correct | 5 ms | 3064 KB | Output is correct |
| 14 | Correct | 5 ms | 3064 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 183 ms | 24440 KB | Output is correct |
| 2 | Correct | 197 ms | 24960 KB | Output is correct |
| 3 | Correct | 203 ms | 28644 KB | Output is correct |
| 4 | Correct | 228 ms | 34416 KB | Output is correct |
| 5 | Correct | 203 ms | 34468 KB | Output is correct |
| 6 | Correct | 246 ms | 37240 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 2936 KB | Output is correct |
| 2 | Correct | 7 ms | 2936 KB | Output is correct |
| 3 | Correct | 8 ms | 2936 KB | Output is correct |
| 4 | Correct | 7 ms | 2936 KB | Output is correct |
| 5 | Correct | 6 ms | 2936 KB | Output is correct |
| 6 | Correct | 6 ms | 3064 KB | Output is correct |
| 7 | Correct | 6 ms | 3064 KB | Output is correct |
| 8 | Correct | 5 ms | 2936 KB | Output is correct |
| 9 | Correct | 5 ms | 2936 KB | Output is correct |
| 10 | Correct | 5 ms | 3064 KB | Output is correct |
| 11 | Correct | 8 ms | 3064 KB | Output is correct |
| 12 | Correct | 5 ms | 2936 KB | Output is correct |
| 13 | Correct | 5 ms | 3064 KB | Output is correct |
| 14 | Correct | 5 ms | 3064 KB | Output is correct |
| 15 | Correct | 183 ms | 24440 KB | Output is correct |
| 16 | Correct | 197 ms | 24960 KB | Output is correct |
| 17 | Correct | 203 ms | 28644 KB | Output is correct |
| 18 | Correct | 228 ms | 34416 KB | Output is correct |
| 19 | Correct | 203 ms | 34468 KB | Output is correct |
| 20 | Correct | 246 ms | 37240 KB | Output is correct |
| 21 | Correct | 160 ms | 23892 KB | Output is correct |
| 22 | Correct | 175 ms | 24564 KB | Output is correct |
| 23 | Correct | 173 ms | 27432 KB | Output is correct |
| 24 | Correct | 196 ms | 34252 KB | Output is correct |
| 25 | Correct | 220 ms | 37776 KB | Output is correct |
| 26 | Correct | 159 ms | 23900 KB | Output is correct |
| 27 | Correct | 174 ms | 24340 KB | Output is correct |
| 28 | Correct | 177 ms | 27512 KB | Output is correct |
| 29 | Correct | 271 ms | 33372 KB | Output is correct |
| 30 | Correct | 228 ms | 35704 KB | Output is correct |
| 31 | Correct | 159 ms | 23968 KB | Output is correct |
| 32 | Correct | 169 ms | 24440 KB | Output is correct |
| 33 | Correct | 189 ms | 28396 KB | Output is correct |
| 34 | Correct | 219 ms | 34040 KB | Output is correct |
| 35 | Correct | 223 ms | 37608 KB | Output is correct |
| 36 | Correct | 213 ms | 34276 KB | Output is correct |