#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 100010, MAX_K = 17;
const ll inf = 1ll << 60, bound = 1e15;
int n, s, q, e;
vector<pair<int,int>> edge[MAX_N];
bool shop[MAX_N];
int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];
ll dp[MAX_K][MAX_N], dep[MAX_N];
inline bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
void dfs(int x, int lst) {
static int t;
in[x] = t++;
anc[0][x] = lst;
dp[0][x] = shop[x] ? dep[x] : inf;
for (auto [u, w] : edge[x]) if (u != lst) {
dep[u] = dep[x] + w;
dfs(u, x);
chmin(dp[0][x], dp[0][u]);
}
DE(x, dep[x], dp[0][x]);
out[x] = t;
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> s >> q >> e;
vector<pair<int,int>> alle(n);
for (int a, b, w, i = 1;i < n;++i) {
cin >> a >> b >> w;
alle[i] = {a, b};
edge[a].pb(b, w);
edge[b].pb(a, w);
}
for (int p, i = 0;i < s;++i) {
cin >> p;
shop[p] = true;
}
dfs(e, e);
for (int i = 1;i <= n;++i) {
dp[0][i] -= 2 * dep[i];
DE(i, dp[0][i]);
}
for (int b = 1;1 << b <= n;++b)
for (int i = 1;i <= n;++i) {
anc[b][i] = anc[b-1][ anc[b-1][i] ];
dp[b][i] = min(dp[b-1][i], dp[b-1][ anc[b-1][i] ]);
}
while (q--) {
int ID, R;
cin >> ID >> R;
auto [a, b] = alle[ID];
if (dep[a] > dep[b]) swap(a, b);
// a is up
// b is down
if (isanc(b, R)) {
if (shop[R]) {
cout << 0 << '\n';
continue;
}
ll res = dp[0][R] - dep[R];
int x = R;
for (int d = __lg(n);d >= 0;--d) {
if (!isanc(anc[d][x], a)) {
DE(x, dp[d][x]);
chmin(res, dp[d][x] + dep[R]);
x = anc[d][x];
}
}
chmin(res, dp[0][x] + dep[R]);
if (res > bound)
cout << "oo\n";
else cout << res << '\n';
}
else cout << "escape\n";
}
}
Compilation message
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:20:17: warning: statement has no effect [-Wunused-value]
20 | #define DE(...) 0
| ^
valley.cpp:47:2: note: in expansion of macro 'DE'
47 | DE(x, dep[x], dp[0][x]);
| ^~
valley.cpp: In function 'int32_t main()':
valley.cpp:20:17: warning: statement has no effect [-Wunused-value]
20 | #define DE(...) 0
| ^
valley.cpp:67:3: note: in expansion of macro 'DE'
67 | DE(i, dp[0][i]);
| ^~
valley.cpp:20:17: warning: statement has no effect [-Wunused-value]
20 | #define DE(...) 0
| ^
valley.cpp:92:6: note: in expansion of macro 'DE'
92 | DE(x, dp[d][x]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
33468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
