제출 #847074

#제출 시각아이디문제언어결과실행 시간메모리
847074dungzValley (BOI19_valley)C++17
0 / 100
2 ms6748 KiB
//dau tuyen //dau tuyen //dau tuyen #pragma GCC optimize ("O2") #include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define endl '\n' #define task "task" #define task "task" #define prll pair<ll,ll> #define pb push_back #define ld long double const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=1e5+5; ll cost[nmax],f[nmax],mn[nmax][25]; int h[nmax],up[nmax][25]; vector<pair<int,ll>> a[nmax]; bool str[nmax]; vector<pair<int,int>> edge; void dfs(int u,int par) { for(auto i:a[u]) { if(i.fi!=par) { cost[i.fi]=cost[u]+i.se; h[i.fi]=h[u]+1; dfs(i.fi,u); } } } void dfs2(int u,int par) { f[u]=MAX; if(str[u]) f[u]=cost[u]; for(auto i:a[u]) { if(i.fi!=par) { dfs2(i.fi,u); f[u]=min(f[u],f[i.fi]); } } } void dfs3(int u,int par) { for(auto i:a[u]) { if(i.fi!=par) { up[i.fi][0]=u; mn[i.fi][0]=f[u]-2*cost[u]; for(int j=1;j<=20;j++) { up[i.fi][j]=up[up[i.fi][j-1]][j-1]; mn[i.fi][j]=min(mn[i.fi][j-1],mn[up[i.fi][j-1]][j-1]); } dfs3(i.fi,u); } } } int main(){ #ifndef ONLINE_JUDGE freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); #endif ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,s,q,e; cin>>n>>s>>q>>e; edge.push_back({0,0}); for(int i=1;i<=n-1;i++) { int x,y,z; cin>>x>>y>>z; a[x].push_back({y,z}); a[y].push_back({x,z}); edge.push_back({x,y}); } for(int i=1;i<=s;i++) { int x; cin>>x; str[x]=1; } dfs(e,0); dfs2(e,0); dfs3(e,0); while(q--) { int u,v; cin>>u>>v; if(h[edge[u].fi]>h[edge[u].se]) swap(edge[u].fi,edge[u].se); // cout<<h[edge[u].se]<<" "<<h[v]<<" "<<edge[u].se<<" "<<v<<endl; if(h[edge[u].fi]>=h[v]) { cout<<"escaped"<<endl; continue; } int gap=-h[edge[u].se]+h[v]; // cout<<gap<<endl; int v2=v; for(int i=0;i<=20;i++) { if(gap&(1<<i)) { gap-=(1<<i); v2=up[v][i]; } } if(v2!=edge[u].se) { cout<<"escaped"<<endl; continue; } gap=-h[edge[u].se]+h[v]; ll ans=MAX; v2=v; for(int i=0;i<=20;i++) { if(gap&(1<<i)) { gap-=(1<<i); ans=min(ans,cost[v2]+mn[v2][i]); v2=up[v2][i]; } } // cout<<f[v]<<" "<<cost[v]<<" "<<ans<<endl; ans=min(ans,f[v]-cost[v]); if(ans>1e15) cout<<"oo"<<endl; else cout<<ans<<endl; } // cout<<mn[5][1]<<cost[3]<<" "<<cost[4]<<" "<<cost[5]<<" "<<f[5]; } /* */

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'int main()':
valley.cpp:66:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |            freopen (task".inp", "r", stdin);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:67:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |            freopen (task".out", "w", stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...