이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
ll mod = 1e9+7 ;
ll power(ll a, ll b)
{
return (!b ? 1 : (b & 1 ? a * power(a * a % mod, b / 2) % mod : power(a * a % mod, b / 2) % mod));
}
const ll N = 1e5+23 , L = 23, INF = 1e18 ;
ll par[N][L] , mn[N][L];
ll dist[N] , distp[N];
ll h[N] , st[N], ft[N] , t;
vector<pll> E, g[N];
ll n , s , q, e;
ll vis[N] ;
void dfs(int v, int p=0){
st[v]=++t;
for (auto pp: g[v]){
int u = pp.F , w= pp.S;
if(u!=p){
par[u][0]=v;
dist[u]= dist[v]+w;
h[u]=h[v]+1;
dfs(u,v);
}
}
ft[v]=++t;
}
void DFS(int v, int p=0){
if(vis[v])distp[v]=dist[v];
else distp[v]=INF;
for (auto pp: g[v]){
int u = pp.F , w= pp.S;
if(u!=p){
DFS(u, v);
distp[v]=min(distp[v] , distp[u]);
}
}
}
ll tof(ll v, ll h){
if(!h) return distp[v];
ll hh= __lg(h);
return min(mn[v][h] , tof(par[v][hh] , h-(1<<hh) ));
}
int main()
{
fast_io
cin>>n>>s>>q>>e;
for (int i=0; i<n-1; i++){
ll u , v, w; cin>>v>>u>>w;
g[v].pb({u,w});
g[u].pb({v, w});
E.pb({u, v});
}
for (int i=0; i<s; i++){
int c; cin>>c;
vis[c]=1;
}
dfs(e);
DFS(e);
for (int i=1; i<=n; i++){
//cout<<distp[i]<<" ";
distp[i]-=(2*dist[i]);
//cout<<distp[i]<<":"<<i<<endl;
}
for (int i=1; i<=n; i++){
if((1<<0)<=h[i]) mn[i][0]= min(distp[i] , distp[par[i][0]]);
}
for (int j=1; j<L; j++){
for (int i=1; i<=n; i++){
if( (1<<(j) <=h[i]) ){
par[i][j]=par[par[i][j-1] ][j-1];
mn[i][j]= min(mn[i][j-1] , mn[par[i][j-1]][j-1]);
}
}
}
while(q--){
int l , b;
cin>>l>>b;
l--;
int u= E[l].S , v= E[l].F;
if(h[v]>h[u]) swap(u,v);
if(st[u]<=st[b] && ft[u]>=ft[b]){
ll d=h[b]-h[u];
ll ans=tof(b, d)+dist[b];
if(ans>1e14){
//cerr<<ans<<":";
cout<<"oo"<<endl;
}
else cout<<ans<<endl;
}
else{
cout<<"escaped"<<endl;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
valley.cpp: In function 'void DFS(int, int)':
valley.cpp:57:24: warning: unused variable 'w' [-Wunused-variable]
57 | int u = pp.F , w= pp.S;
| ^
# | 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... |