//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
const long long oo = 1e18;
long long dp[N + 1], f[N + 1];
int n, s, q, root, tin[N + 1], depth[N + 1], tout[N + 1], timer, l[N], r[N], w[N];
vector<int> adj[N + 1];
vector<pair<int, int> > query[N + 1];
bool shop[N + 1];
long long res[N + 1];
void read()
{
cin >> n >> s >> q >> root;
for (int i = 1; i < n; ++ i)
{
cin >> l[i] >> r[i] >> w[i];
adj[l[i]].push_back(i);
adj[r[i]].push_back(i);
}
for (int i = 1; i <= s; ++ i)
{
int u;
cin >> u;
shop[u] = true;
}
for (int i = 1; i <= q; ++ i)
{
int I, R;
cin >> I >> R;
query[R].push_back({I, i});
}
depth[root] = 1;
fill(res, res + q + 1, oo);
}
struct FenwickTree
{
multiset<long long> tree[N + 1];
void add(int pos, long long val)
{
for (; pos > 0; pos -= (pos & (-pos)))
{
tree[pos].insert(val);
}
}
long long get(int pos)
{
long long ret = oo;
for (; pos <= n; pos += (pos & (-pos)))
{
if (!tree[pos].empty())
{
ret = min(ret, *tree[pos].begin());
}
}
return ret;
}
void del(int pos, long long val)
{
for (; pos > 0; pos -= (pos & (-pos)))
{
auto it = tree[pos].find(val);
if (it != tree[pos].end())
{
tree[pos].erase(it);
}
}
}
} tree;
void preDFS(int u, int p)
{
tin[u] = ++timer;
if (shop[u])
{
dp[u] = f[u];
}
else
{
dp[u] = oo;
}
for (int i : adj[u])
{
int v = l[i] ^ r[i] ^ u;
if (v == p)
{
continue;
}
f[v] = f[u] + w[i];
depth[v] = depth[u] + 1;
preDFS(v, u);
dp[u] = min(dp[u], dp[v]);
}
tout[u] = timer;
}
void DFS(int u, int p)
{
if (dp[u] != oo)
{
tree.add(depth[u], dp[u] - 2 * f[u]);
}
for (auto &x : query[u])
{
if (depth[l[x.first]] > depth[r[x.first]])
{
swap(l[x.first], r[x.first]);
}
int b = r[x.first];
if (tin[u] < tin[b] || tin[u] > tout[b])
{
res[x.second] = -1;
continue;
}
long long t = tree.get(depth[b]);
if (t != oo)
{
res[x.second] = t + f[u];
}
}
for (int i : adj[u])
{
int v = l[i] ^ r[i] ^ u;
if (v == p)
{
continue;
}
DFS(v, u);
}
if (dp[u] != oo)
{
tree.del(depth[u], dp[u] - 2 * f[u]);
}
}
void solve()
{
preDFS(root, 0);
DFS(root, 0);
for (int i = 1; i <= q; ++ i)
{
if (res[i] == -1)
{
cout << "escaped" << '\n';
}
else if (res[i] == oo)
{
cout << "oo" << '\n';
}
else
{
cout << res[i] << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
10068 KB |
Output is correct |
2 |
Correct |
8 ms |
10124 KB |
Output is correct |
3 |
Correct |
7 ms |
10088 KB |
Output is correct |
4 |
Correct |
9 ms |
10068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
10068 KB |
Output is correct |
2 |
Correct |
8 ms |
10124 KB |
Output is correct |
3 |
Correct |
7 ms |
10088 KB |
Output is correct |
4 |
Correct |
9 ms |
10068 KB |
Output is correct |
5 |
Correct |
7 ms |
9812 KB |
Output is correct |
6 |
Correct |
8 ms |
9800 KB |
Output is correct |
7 |
Correct |
6 ms |
9940 KB |
Output is correct |
8 |
Correct |
7 ms |
9828 KB |
Output is correct |
9 |
Correct |
6 ms |
9868 KB |
Output is correct |
10 |
Correct |
7 ms |
9868 KB |
Output is correct |
11 |
Correct |
7 ms |
9868 KB |
Output is correct |
12 |
Correct |
9 ms |
9856 KB |
Output is correct |
13 |
Correct |
6 ms |
9928 KB |
Output is correct |
14 |
Correct |
7 ms |
9940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
24364 KB |
Output is correct |
2 |
Correct |
209 ms |
24156 KB |
Output is correct |
3 |
Correct |
223 ms |
24132 KB |
Output is correct |
4 |
Correct |
261 ms |
34260 KB |
Output is correct |
5 |
Correct |
213 ms |
32804 KB |
Output is correct |
6 |
Correct |
305 ms |
46636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
10068 KB |
Output is correct |
2 |
Correct |
8 ms |
10124 KB |
Output is correct |
3 |
Correct |
7 ms |
10088 KB |
Output is correct |
4 |
Correct |
9 ms |
10068 KB |
Output is correct |
5 |
Correct |
7 ms |
9812 KB |
Output is correct |
6 |
Correct |
8 ms |
9800 KB |
Output is correct |
7 |
Correct |
6 ms |
9940 KB |
Output is correct |
8 |
Correct |
7 ms |
9828 KB |
Output is correct |
9 |
Correct |
6 ms |
9868 KB |
Output is correct |
10 |
Correct |
7 ms |
9868 KB |
Output is correct |
11 |
Correct |
7 ms |
9868 KB |
Output is correct |
12 |
Correct |
9 ms |
9856 KB |
Output is correct |
13 |
Correct |
6 ms |
9928 KB |
Output is correct |
14 |
Correct |
7 ms |
9940 KB |
Output is correct |
15 |
Correct |
170 ms |
24364 KB |
Output is correct |
16 |
Correct |
209 ms |
24156 KB |
Output is correct |
17 |
Correct |
223 ms |
24132 KB |
Output is correct |
18 |
Correct |
261 ms |
34260 KB |
Output is correct |
19 |
Correct |
213 ms |
32804 KB |
Output is correct |
20 |
Correct |
305 ms |
46636 KB |
Output is correct |
21 |
Correct |
146 ms |
23792 KB |
Output is correct |
22 |
Correct |
209 ms |
23484 KB |
Output is correct |
23 |
Correct |
194 ms |
23504 KB |
Output is correct |
24 |
Correct |
207 ms |
26292 KB |
Output is correct |
25 |
Correct |
196 ms |
32004 KB |
Output is correct |
26 |
Correct |
148 ms |
23892 KB |
Output is correct |
27 |
Correct |
176 ms |
23596 KB |
Output is correct |
28 |
Correct |
174 ms |
23756 KB |
Output is correct |
29 |
Correct |
244 ms |
30492 KB |
Output is correct |
30 |
Correct |
278 ms |
38016 KB |
Output is correct |
31 |
Correct |
153 ms |
23992 KB |
Output is correct |
32 |
Correct |
177 ms |
23764 KB |
Output is correct |
33 |
Correct |
180 ms |
23912 KB |
Output is correct |
34 |
Correct |
249 ms |
33656 KB |
Output is correct |
35 |
Correct |
288 ms |
49928 KB |
Output is correct |
36 |
Correct |
257 ms |
33780 KB |
Output is correct |