# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
282036 | bigg | Valley (BOI19_valley) | C++14 | 218 ms | 38008 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;
typedef long long ll;
const ll INF = 1e18;
const int MAXN = 1e5 + 10;
const int MAXL = 23;
int n;
vector<pair<int, int > >grafo[MAXN];
int tin[MAXN], tout[MAXN], altura[MAXN];
int sparse[MAXN][MAXL];
ll dist[MAXN], dpaux[MAXN], dp[MAXN][MAXL];
bool isshop[MAXN];
int T;
void dfs(int x, int p){
//printf("oi\n");
tin[x] = ++T;
if(isshop[x])dpaux[x] = dist[x];
else dpaux[x] = INF;
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;//, id = grafo[x][i].second.first;
if(viz == p /*|| id == ip*/) continue;
altura[viz] = altura[x] + 1;
dist[viz] = dist[x] + grafo[x][i].second;
dfs(viz, x);
dpaux[x] = min(dpaux[x], dpaux[viz]);
}
//if(dpaux[x] < INF) dpaux[x] -= 2*dist[x];
tout[x] =T;
}
void dfs2(int x, int p){
//printf("%d %d\n",x, p );
dp[x][0] = dpaux[x];
for(int k = 1; k < MAXL; k++){
sparse[x][k] = sparse[sparse[x][k-1]][k-1];
dp[x][k] = min(dp[x][k-1], dp[sparse[x][k-1]][k-1]);
}
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(viz == p) continue;
sparse[viz][0] = x;
dfs2(viz, x);
}
}
bool checkin(int id1, int id2){
if(tin[id1] <= tin[id2] && tout[id1] >= tin[id2] ) return true;
return false;
}
ll query(int x, int p){
ll ans = INF;
for(int k = MAXL - 1; k >= 0; k--){
if(checkin(sparse[x][k], p)){
ans = min(ans, dp[x][k]);
x = sparse[x][k];
}
}
ans = min(ans, dpaux[p]);
return ans;
}
int s, e, q;
//std::vector<int> shops;
pair<int, int> arestas[MAXN];
int main(){
scanf("%d %d %d %d", &n, &s, &q, &e);
for(int i = 1; i < n; i++){
int u, v;
ll w;
scanf("%d %d %lld", &u, &v, &w);
grafo[u].push_back(make_pair(v, w));
grafo[v].push_back(make_pair(u, w));
arestas[i] = make_pair(u, v);
}
for(int i = 0; i < s; i++){
int k;
scanf("%d", &k);
isshop[k] = 1;
}
dfs(e, 0);
for(int i = 1; i <= n; i++){
if(dpaux[i] < INF) dpaux[i] -= 2*dist[i];
}
dfs2(e, 0);
for(int i = 1; i <= q; i++){
//printf("kkk\n");
int id, k;
scanf("%d %d", &id, &k);
int u = arestas[id].first, v = arestas[id].second;
if(altura[u] < altura[v]) swap(u, v);
if(checkin(u, k)){
//if(isshop[k]) printf("0\n");
if(query(k,u) < INF)printf("%lld\n", dist[k] + query(k, u) );
else printf("oo\n");
}
else printf("escaped\n");
}
}
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... |