# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
123029 |
2019-06-30T04:49:14 Z |
luciocf |
Valley (BOI19_valley) |
C++14 |
|
353 ms |
46584 KB |
// BOI 2019 - Alpine Valley
// Lúcio Cardoso
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int maxn = 1e5+10;
const int maxl = 20;
const long long inf = 2e18+10;
typedef long long ll;
typedef pair<int, int> pii;
int n, s, q, e;
int w[maxn];
int pai[maxn], nivel[maxn];
ll dist[maxn], sub[maxn];
pair<int, ll> tab[maxn][maxl];
bool shop[maxn];
pii edge[maxn];
vector<pii> grafo[maxn];
void dfs(int u, int p)
{
if (shop[u]) sub[u] = 0;
for (auto pp: grafo[u])
{
int v = pp.first, d = w[pp.second];
if (v == p) continue;
pai[v] = u, nivel[v] = nivel[u]+1;
dist[v] = dist[u]+1ll*d;
dfs(v, u);
sub[u] = min(sub[u], sub[v]+1ll*d);
}
}
void build(void)
{
for (int i = 1; i <= n; i++)
{
tab[i][0].ff = pai[i];
tab[i][0].ss = inf;
if (sub[i] != inf) tab[i][0].ss = min(tab[i][0].ss, sub[i]-dist[i]);
if (sub[pai[i]] != inf) tab[i][0].ss = min(tab[i][0].ss, sub[pai[i]]-dist[pai[i]]);
}
for (int j = 1; j < maxl; j++)
{
for (int i = 1; i <= n; i++)
{
tab[i][j].ff = tab[tab[i][j-1].ff][j-1].ff;
tab[i][j].ss = min(tab[i][j-1].ss, tab[tab[i][j-1].ff][j-1].ss);
}
}
}
int lca(int u, int v)
{
if (nivel[u] < nivel[v]) swap(u, v);
for (int i = maxl-1; i >= 0; i--)
if (nivel[u] - (1<<i) >= nivel[v])
u = tab[u][i].ff;
if (u == v) return u;
for (int i = maxl-1; i >= 0; i--)
if (tab[u][i].ff && tab[v][i].ff && tab[u][i].ff != tab[v][i].ff)
u = tab[u][i].ff, v = tab[v][i].ff;
return pai[u];
}
ll get(int u, int v)
{
ll ans = (sub[u] == inf ? inf : sub[u]-dist[u]);
for (int i = maxl-1; i >= 0; i--)
if (nivel[u] - (1<<i) >= nivel[v])
ans = min(ans, tab[u][i].ss), u = tab[u][i].ff;
return ans;
}
int main(void)
{
scanf("%d %d %d %d", &n, &s, &q, &e);
for (int i = 1; i < n; i++)
{
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
w[i] = c, edge[i] = {u, v};
grafo[u].push_back({v, i}); grafo[v].push_back({u, i});
}
for (int i = 1; i <= s; i++)
{
int c;
scanf("%d", &c);
shop[c] = 1;
}
for (int i = 1; i <= n; i++)
sub[i] = inf;
dfs(e, 0); build();
for (int i = 1; i <= q; i++)
{
int u, r;
scanf("%d %d", &r, &u);
int a = edge[r].first, b = edge[r].second;
if (nivel[a] > nivel[b]) swap(a, b);
if (lca(u, b) != b) printf("escaped\n");
else
{
ll ans = get(u, b);
if (ans == inf) printf("oo\n");
else printf("%lld\n", ans+dist[u]);
}
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &s, &q, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c);
~~~~~^~~~~~~~~~
valley.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &r, &u);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
2808 KB |
Output is correct |
2 |
Correct |
8 ms |
2808 KB |
Output is correct |
3 |
Correct |
8 ms |
2808 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
2808 KB |
Output is correct |
2 |
Correct |
8 ms |
2808 KB |
Output is correct |
3 |
Correct |
8 ms |
2808 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
5 ms |
3064 KB |
Output is correct |
6 |
Correct |
5 ms |
3064 KB |
Output is correct |
7 |
Correct |
5 ms |
3064 KB |
Output is correct |
8 |
Correct |
5 ms |
3064 KB |
Output is correct |
9 |
Correct |
5 ms |
3064 KB |
Output is correct |
10 |
Correct |
5 ms |
3064 KB |
Output is correct |
11 |
Correct |
5 ms |
3064 KB |
Output is correct |
12 |
Correct |
5 ms |
3064 KB |
Output is correct |
13 |
Correct |
5 ms |
3192 KB |
Output is correct |
14 |
Correct |
5 ms |
3192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
42248 KB |
Output is correct |
2 |
Correct |
236 ms |
41820 KB |
Output is correct |
3 |
Correct |
277 ms |
41848 KB |
Output is correct |
4 |
Correct |
280 ms |
43640 KB |
Output is correct |
5 |
Correct |
328 ms |
43704 KB |
Output is correct |
6 |
Correct |
353 ms |
45524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
2808 KB |
Output is correct |
2 |
Correct |
8 ms |
2808 KB |
Output is correct |
3 |
Correct |
8 ms |
2808 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
5 ms |
3064 KB |
Output is correct |
6 |
Correct |
5 ms |
3064 KB |
Output is correct |
7 |
Correct |
5 ms |
3064 KB |
Output is correct |
8 |
Correct |
5 ms |
3064 KB |
Output is correct |
9 |
Correct |
5 ms |
3064 KB |
Output is correct |
10 |
Correct |
5 ms |
3064 KB |
Output is correct |
11 |
Correct |
5 ms |
3064 KB |
Output is correct |
12 |
Correct |
5 ms |
3064 KB |
Output is correct |
13 |
Correct |
5 ms |
3192 KB |
Output is correct |
14 |
Correct |
5 ms |
3192 KB |
Output is correct |
15 |
Correct |
208 ms |
42248 KB |
Output is correct |
16 |
Correct |
236 ms |
41820 KB |
Output is correct |
17 |
Correct |
277 ms |
41848 KB |
Output is correct |
18 |
Correct |
280 ms |
43640 KB |
Output is correct |
19 |
Correct |
328 ms |
43704 KB |
Output is correct |
20 |
Correct |
353 ms |
45524 KB |
Output is correct |
21 |
Correct |
183 ms |
42204 KB |
Output is correct |
22 |
Correct |
206 ms |
41880 KB |
Output is correct |
23 |
Correct |
221 ms |
41692 KB |
Output is correct |
24 |
Correct |
249 ms |
43952 KB |
Output is correct |
25 |
Correct |
266 ms |
46584 KB |
Output is correct |
26 |
Correct |
193 ms |
42232 KB |
Output is correct |
27 |
Correct |
216 ms |
42104 KB |
Output is correct |
28 |
Correct |
223 ms |
41876 KB |
Output is correct |
29 |
Correct |
266 ms |
43256 KB |
Output is correct |
30 |
Correct |
296 ms |
44772 KB |
Output is correct |
31 |
Correct |
209 ms |
42424 KB |
Output is correct |
32 |
Correct |
214 ms |
41976 KB |
Output is correct |
33 |
Correct |
240 ms |
42060 KB |
Output is correct |
34 |
Correct |
262 ms |
43776 KB |
Output is correct |
35 |
Correct |
264 ms |
46456 KB |
Output is correct |
36 |
Correct |
233 ms |
44408 KB |
Output is correct |