#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 * 1000 + 7;
const ll I = 1000000LL * 1000000LL * 1000000LL;
int lca[20][N], poz[N], czy[N], od[N];
ll dol[3][N], gor[N], nws[20][N], rnws[20][N], odl[N];
vector<pair<int, ll>> kr[N];
pair<int, int> ed[N];
void DFS(int v)
{
od[v] = 1;
int i;
ll aw;
dol[0][v] = I;
dol[1][v] = I;
dol[2][v] = I;
if(czy[v] == 1)
dol[0][v] = 0;
gor[v] = I;
for(i = 0; i < (int)kr[v].size(); ++i)
{
if(od[kr[v][i].first] == 1)
continue;
if(dol[0][v] == dol[0][kr[v][i].first] + kr[v][i].second)
rnws[0][kr[v][i].first] = dol[1][v];
else
rnws[0][kr[v][i].first] = dol[0][v];
poz[kr[v][i].first] = poz[v] + 1;
odl[kr[v][i].first] = odl[v] + kr[v][i].second;
lca[0][kr[v][i].first] = v;
DFS(kr[v][i].first);
aw = dol[0][kr[v][i].first] + kr[v][i].second;
if(aw < dol[0][v])
swap(aw, dol[0][v]);
if(aw < dol[1][v])
swap(aw, dol[1][v]);
if(aw < dol[2][v])
swap(aw, dol[2][v]);
}
}
void DFS2(int v, int o)
{
od[v] = 1;
int i;
if(czy[v] == 1)
gor[v] = 0LL;
nws[0][v] = dol[0][v];
for(i = 0; i < (int)kr[v].size(); ++i)
{
if(od[kr[v][i].first] == 1)
continue;
gor[kr[v][i].first] = gor[v];
if(dol[0][kr[v][i].first] + kr[v][i].second == dol[0][v])
gor[kr[v][i].first] = min(gor[kr[v][i].first], dol[1][v] + kr[v][i].second);
else
gor[kr[v][i].first] = min(gor[kr[v][i].first], dol[0][v] + kr[v][i].second);
DFS2(kr[v][i].first, o);
}
}
void WyLCA(int n)
{
int i, j;
for(j = 1; j <= 18; ++j)
{
for(i = 1; i <= n; ++i)
{
lca[j][i] = lca[j - 1][lca[j - 1][i]];
nws[j][i] = min(nws[j - 1][i], nws[j - 1][lca[j - 1][i]] + odl[i] - odl[lca[j - 1][i]]);
rnws[j][i] = min(rnws[j - 1][lca[j - 1][i]], rnws[j - 1][i] + odl[lca[j - 1][i]] - lca[j][i]);
}
}
}
pair<int, ll> LCA(int a, int b)
{
int i, pa, pb;
if(a == b)
return make_pair(a, dol[0][a]);
pa = a;
pb = b;
ll w1, w2;
w1 = I;
w2 = I;
if(poz[a] > poz[b])
{
for(i = 18; i >= 0; --i)
{
if(poz[lca[i][a]] > poz[b])
{
w1 = min(w1, nws[i][a] + odl[pa] - odl[a]);
a = lca[i][a];
}
}
if(lca[0][a] == b)
{
w1 = min(w1, odl[pa] - odl[b] + dol[0][b]);
}
w1 = min(w1, nws[0][a] + odl[pa] - odl[a]);
a = lca[0][a];
//cout << a << " " << b << "\n";
}
if(poz[b] > poz[a])
{
for(i = 18; i >= 0; --i)
{
if(poz[lca[i][b]] > poz[a])
{
w2 = min(w2 + odl[b] - odl[lca[i][b]], rnws[i][b]);
b = lca[i][b];
}
}
w2 = min(w2 + odl[b] - odl[lca[0][b]], rnws[0][b]);
b = lca[0][b];
}
if(b == pa)
{
return make_pair(b, min(min(w1, w2), gor[a]));
}
if(a == pb)
{
return make_pair(a, min(w1, w2));
}
for(i = 18; i >= 0; --i)
{
if(lca[i][a] != lca[i][b])
{
w2 = min(w2 + odl[b] - odl[lca[i][b]], rnws[i][b]);
b = lca[i][b];
w1 = min(w1, nws[i][a] + odl[pa] - odl[a]);
a = lca[i][a];
}
}
w2 = min(w2 + odl[b] - odl[lca[0][b]], rnws[0][b]);
b = lca[0][b];
w1 = min(w1, nws[0][a] + odl[pa] - odl[a]);
a = lca[0][a];
w2 += (odl[pa] - odl[a]);
w1 = min(w1, gor[a]);
return make_pair(a, min(w1, w2));
}
void Wyw(int s, int n)
{
int i, j;
for(i = 1; i <= n; ++i)
{
for(j = 0; j <= 18; ++j)
{
nws[j][i] = I;
rnws[j][i] = I;
}
}
poz[s] = 0;
odl[s] = 0LL;
lca[0][s] = s;
DFS(s);
for(i = 1; i <= n; ++i)
od[i] = 0;
DFS2(s, s);
}
void Odp(int q)
{
int i, v, x, a, b;
pair<int, ll> w;
for(i = 1; i <= q; ++i)
{
cin >> x >> v;
a = ed[x].first;
b = ed[x].second;
if(poz[a] < poz[b])
w = LCA(v, b);
else
w = LCA(v, a);
//cout << w.first << " " << LCA(v, b).first << "\n";
if(poz[w.first] <= min(poz[a], poz[b]))
{
cout << "escaped\n";
}
else
{
if(w.second >= I)
cout << "oo\n";
else
cout << w.second << "\n";
}
}
}
void Wczytaj(int &n, int &s, int &q)
{
int i, k, a;
ll d;
cin >> n >> k >> q >> s;
for(i = 1; i < n; ++i)
{
cin >> ed[i].first >> ed[i].second >> d;
kr[ed[i].first].push_back(make_pair(ed[i].second, d));
kr[ed[i].second].push_back(make_pair(ed[i].first, d));
}
for(i = 1; i <= k; ++i)
{
cin >> a;
czy[a] = 1;
}
}
void Valley()
{
int n, s, q;
Wczytaj(n, s, q);
Wyw(s, n);
WyLCA(n);
Odp(q);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Valley();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3148 KB |
Output is correct |
2 |
Correct |
6 ms |
3204 KB |
Output is correct |
3 |
Correct |
6 ms |
3148 KB |
Output is correct |
4 |
Correct |
6 ms |
3148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3148 KB |
Output is correct |
2 |
Correct |
6 ms |
3204 KB |
Output is correct |
3 |
Correct |
6 ms |
3148 KB |
Output is correct |
4 |
Correct |
6 ms |
3148 KB |
Output is correct |
5 |
Correct |
3 ms |
3532 KB |
Output is correct |
6 |
Correct |
3 ms |
3460 KB |
Output is correct |
7 |
Correct |
4 ms |
3456 KB |
Output is correct |
8 |
Correct |
3 ms |
3528 KB |
Output is correct |
9 |
Correct |
3 ms |
3404 KB |
Output is correct |
10 |
Correct |
4 ms |
3532 KB |
Output is correct |
11 |
Correct |
3 ms |
3532 KB |
Output is correct |
12 |
Correct |
3 ms |
3532 KB |
Output is correct |
13 |
Correct |
5 ms |
3532 KB |
Output is correct |
14 |
Correct |
5 ms |
3532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
238 ms |
55364 KB |
Output is correct |
2 |
Correct |
250 ms |
55116 KB |
Output is correct |
3 |
Correct |
328 ms |
55424 KB |
Output is correct |
4 |
Correct |
451 ms |
57276 KB |
Output is correct |
5 |
Correct |
425 ms |
57368 KB |
Output is correct |
6 |
Correct |
483 ms |
59540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3148 KB |
Output is correct |
2 |
Correct |
6 ms |
3204 KB |
Output is correct |
3 |
Correct |
6 ms |
3148 KB |
Output is correct |
4 |
Correct |
6 ms |
3148 KB |
Output is correct |
5 |
Correct |
3 ms |
3532 KB |
Output is correct |
6 |
Correct |
3 ms |
3460 KB |
Output is correct |
7 |
Correct |
4 ms |
3456 KB |
Output is correct |
8 |
Correct |
3 ms |
3528 KB |
Output is correct |
9 |
Correct |
3 ms |
3404 KB |
Output is correct |
10 |
Correct |
4 ms |
3532 KB |
Output is correct |
11 |
Correct |
3 ms |
3532 KB |
Output is correct |
12 |
Correct |
3 ms |
3532 KB |
Output is correct |
13 |
Correct |
5 ms |
3532 KB |
Output is correct |
14 |
Correct |
5 ms |
3532 KB |
Output is correct |
15 |
Correct |
238 ms |
55364 KB |
Output is correct |
16 |
Correct |
250 ms |
55116 KB |
Output is correct |
17 |
Correct |
328 ms |
55424 KB |
Output is correct |
18 |
Correct |
451 ms |
57276 KB |
Output is correct |
19 |
Correct |
425 ms |
57368 KB |
Output is correct |
20 |
Correct |
483 ms |
59540 KB |
Output is correct |
21 |
Correct |
239 ms |
54416 KB |
Output is correct |
22 |
Correct |
296 ms |
54292 KB |
Output is correct |
23 |
Correct |
278 ms |
54488 KB |
Output is correct |
24 |
Correct |
340 ms |
56540 KB |
Output is correct |
25 |
Correct |
479 ms |
59484 KB |
Output is correct |
26 |
Correct |
228 ms |
54664 KB |
Output is correct |
27 |
Correct |
349 ms |
54448 KB |
Output is correct |
28 |
Correct |
281 ms |
54704 KB |
Output is correct |
29 |
Correct |
369 ms |
56164 KB |
Output is correct |
30 |
Correct |
402 ms |
57760 KB |
Output is correct |
31 |
Correct |
229 ms |
54864 KB |
Output is correct |
32 |
Correct |
271 ms |
54720 KB |
Output is correct |
33 |
Correct |
309 ms |
55148 KB |
Output is correct |
34 |
Correct |
426 ms |
56884 KB |
Output is correct |
35 |
Correct |
450 ms |
59844 KB |
Output is correct |
36 |
Correct |
378 ms |
56832 KB |
Output is correct |