# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
282039 | 2020-08-23T20:47:23 Z | bigg | Valley (BOI19_valley) | C++14 | 307 ms | 44792 KB |
#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], hasshop[MAXN]; int T; void dfs(int x, int p){ //printf("oi\n"); tin[x] = ++T; hasshop[x] = isshop[x]; 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]); hasshop[x] |= hasshop[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(p, sparse[x][k])){ 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(hasshop[u])printf("%lld\n", dist[k] + query(k, u) ); else printf("oo\n"); } else printf("escaped\n"); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2816 KB | Output is correct |
2 | Correct | 5 ms | 2944 KB | Output is correct |
3 | Correct | 8 ms | 2816 KB | Output is correct |
4 | Correct | 5 ms | 2816 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2816 KB | Output is correct |
2 | Correct | 5 ms | 2944 KB | Output is correct |
3 | Correct | 8 ms | 2816 KB | Output is correct |
4 | Correct | 5 ms | 2816 KB | Output is correct |
5 | Correct | 3 ms | 3072 KB | Output is correct |
6 | Correct | 3 ms | 3072 KB | Output is correct |
7 | Correct | 3 ms | 3072 KB | Output is correct |
8 | Correct | 3 ms | 3072 KB | Output is correct |
9 | Correct | 3 ms | 3072 KB | Output is correct |
10 | Correct | 3 ms | 3072 KB | Output is correct |
11 | Correct | 3 ms | 3072 KB | Output is correct |
12 | Correct | 3 ms | 3072 KB | Output is correct |
13 | Correct | 3 ms | 3072 KB | Output is correct |
14 | Correct | 4 ms | 3072 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 200 ms | 38008 KB | Output is correct |
2 | Correct | 225 ms | 37752 KB | Output is correct |
3 | Correct | 242 ms | 37752 KB | Output is correct |
4 | Correct | 284 ms | 39032 KB | Output is correct |
5 | Correct | 240 ms | 39160 KB | Output is correct |
6 | Correct | 307 ms | 40568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2816 KB | Output is correct |
2 | Correct | 5 ms | 2944 KB | Output is correct |
3 | Correct | 8 ms | 2816 KB | Output is correct |
4 | Correct | 5 ms | 2816 KB | Output is correct |
5 | Correct | 3 ms | 3072 KB | Output is correct |
6 | Correct | 3 ms | 3072 KB | Output is correct |
7 | Correct | 3 ms | 3072 KB | Output is correct |
8 | Correct | 3 ms | 3072 KB | Output is correct |
9 | Correct | 3 ms | 3072 KB | Output is correct |
10 | Correct | 3 ms | 3072 KB | Output is correct |
11 | Correct | 3 ms | 3072 KB | Output is correct |
12 | Correct | 3 ms | 3072 KB | Output is correct |
13 | Correct | 3 ms | 3072 KB | Output is correct |
14 | Correct | 4 ms | 3072 KB | Output is correct |
15 | Correct | 200 ms | 38008 KB | Output is correct |
16 | Correct | 225 ms | 37752 KB | Output is correct |
17 | Correct | 242 ms | 37752 KB | Output is correct |
18 | Correct | 284 ms | 39032 KB | Output is correct |
19 | Correct | 240 ms | 39160 KB | Output is correct |
20 | Correct | 307 ms | 40568 KB | Output is correct |
21 | Correct | 177 ms | 41208 KB | Output is correct |
22 | Correct | 212 ms | 41036 KB | Output is correct |
23 | Correct | 208 ms | 40824 KB | Output is correct |
24 | Correct | 232 ms | 42360 KB | Output is correct |
25 | Correct | 297 ms | 44792 KB | Output is correct |
26 | Correct | 186 ms | 41336 KB | Output is correct |
27 | Correct | 206 ms | 41080 KB | Output is correct |
28 | Correct | 209 ms | 40952 KB | Output is correct |
29 | Correct | 261 ms | 42104 KB | Output is correct |
30 | Correct | 296 ms | 43128 KB | Output is correct |
31 | Correct | 183 ms | 41336 KB | Output is correct |
32 | Correct | 205 ms | 41080 KB | Output is correct |
33 | Correct | 217 ms | 41080 KB | Output is correct |
34 | Correct | 258 ms | 42488 KB | Output is correct |
35 | Correct | 272 ms | 44664 KB | Output is correct |
36 | Correct | 236 ms | 42616 KB | Output is correct |