이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#pragma GCC optimization("g", on)
//#pragma GCC optimize ("inline")
//#pragma GCC optimization("03")
//#pragma GCC optimization("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popused,abm,mmx,avx,tune=native")
using namespace std;
const int N = 1e6 + 5;
const long long inf = 1e18;
const int K = 25;
#define ll long long
#define int long long
#define F first
#define S second
#define pb push_back
int n, s, q, e, p[N], a[N], b[N], dp[N], dist[N], tin[N], tout[N], timer, mn[N][50], up[N][50];
vector<pair<int, int>> g[N];
void dfs(int v, int pr){
tin[v] = timer++;
up[v][0] = pr;
for(auto to : g[v]){
if(to.F != pr){
dist[to.F] = dist[v] + to.S;
dfs(to.F, v);
p[v] = min(p[v], p[to.F] + to.S);
}
}
dp[v] = p[v] - dist[v];
tout[v] = timer++;
}
bool is(int a, int b){
if(tin[a] <= tin[b] && tout[b] <= tout[a]) return 1;
else return 0;
}
void build(int v, int pr){
mn[v][0] = inf;
mn[v][0] = min(dp[v], mn[pr][0]);
for(int i = 1; i <= K; ++i){
up[v][i] = up[up[v][i - 1]][i - 1];
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
}
for(auto to : g[v])
if(to.F != pr)
build(to.F, v);
}
int lift(int u, int v){
if(is(u, v)) return inf;
int res = dp[v], x = v;
for(int i = K; i >= 0; --i){
if(is(u, up[x][i])){
res = min(res, mn[x][i]);
x = up[x][i];
}
}
return res + dist[v];
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s >> q >> e;
for(int i = 1; i <= n; ++i){
p[i] = inf;
}
for(int i = 1, u, v, w; i < n; ++i){
cin >> u >> v >> w;
g[u].pb({v, w});
g[v].pb({u, w});
a[i] = u;
b[i] = v;
}
for(int i = 1, j; i <= s; ++i){
cin >> j;
p[j] = 0;
}
dfs(e, e);
build(e, e);
while(q--){
int i, v, f;
cin >> i >> v;
if(up[a[i]][0] == b[i]) f = a[i];
else f = b[i];
if(!is(f, v)) cout << "escaped\n";
else if(p[f] == inf) cout << "oo\n";
else cout << lift(f, v) << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
valley.cpp:68:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |