제출 #753177

#제출 시각아이디문제언어결과실행 시간메모리
753177aminValley (BOI19_valley)C++14
0 / 100
269 ms51244 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long ll p[21][100000],mi[21][100000]; ll ans=1000000000; int get(int x,int y) { if(y<0) return 0; int u=1; int k=0; //cout<<x<<' '; while(k<=20&&y>0) { if((u&y)==u) { x=p[k][x]; // cout<<k<<' '; ans=min(ans,mi[k][x]); } u*=2; k++; } //cout<<endl; return x; } vector<int>v[100000]; vector<int>w[100000]; int m[100000]; ll val[100000]; ll dist[100000]; int u[1000000]; void dfs(int in,int pa) { val[in]=1e18; for(int i=0;i<v[in].size();i++) { if(v[in][i]==pa) { continue ; } p[0][v[in][i]]=in; dist[v[in][i]]=dist[in]+w[in][i]; u[v[in][i]]=u[in]+1; dfs(v[in][i],in); val[in]=min(val[in],val[v[in][i]]+w[in][i]); } if(m[in]==1) val[in]=0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("balancing.in","r",stdin); // freopen("balancing.out","w",stdout); int n,s,q,e; cin>>n>>s>>q>>e; int a[n],b[n],c[n]; e--; for(int i=0;i<n-1;i++) { cin>>a[i]>>b[i]>>c[i]; a[i]--; b[i]--; v[a[i]].push_back(b[i]); w[a[i]].push_back(c[i]); v[b[i]].push_back(a[i]); w[b[i]].push_back(c[i]); } for(int i=0;i<s;i++) { int z; cin>>z; z--; m[z]=1; } dfs(e,e); for(int i=0;i<n;i++) { val[i]-=dist[i]; mi[0][i]=val[i]; //cout<<dist[i]<<' '; } //cout<<endl; for(int i=1;i<20;i++) { for(int y=0;y<n;y++) { p[i][y]=p[i-1][p[i-1][y]]; mi[i][y]=min(mi[i-1][y],mi[i-1][p[i-1][y]]); } } while(q--) { int x,y; cin>>x>>y; swap(x,y); // cout<<111<<endl; y--; x--; int st,en; st=b[y]; en=a[y]; if(dist[a[y]]<dist[b[y]]) { st=a[y]; en=b[y]; } //cout<<222<<endl; int di=u[x]-u[en]; ans=1000000000000000000; int c=get(x,di); //cout<<c<<endl; //cout<<333<<endl; if(c!=en||di<0) { cout<<"escaped"<<endl; continue; } if(min(val[x]+dist[x],dist[x]+ans)<100000000000000000) cout<<min(val[x]+dist[x],dist[x]+ans)<<endl; else cout<<"oo"<<endl; } }

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

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<v[in].size();i++)
      |                 ~^~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:114:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  114 |     int st,en;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...