제출 #640097

#제출 시각아이디문제언어결과실행 시간메모리
640097StefanSebezValley (BOI19_valley)C++14
0 / 100
308 ms29884 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll N=1e5+50; const ll inf=1e18+50; bool store[N]; bool escaped[N]; ll U[N],V[N],W[N]; ll depth[N],ct=0; ll dp[N]; ll parent[N]; vector<pair<ll,ll>>E[N]; vector<pair<ll,ll>>query[N]; vector<ll>nodes; ll res[N]; ll pref[N]; void DFSsetup(ll u) { if(store[u]==true) { dp[u]=0; } ct++; depth[u]=ct; pref[u]+=pref[parent[u]]; for(auto i:E[u]) { if(i.first!=parent[u]) { parent[i.first]=u; pref[i.first]+=i.second; DFSsetup(i.first); dp[u]=min(dp[u],dp[i.first]+i.second); } } ct--; } void DFSexit(ll u) { nodes.push_back(u); for(ll i=0;i<query[u].size();i++) { ll x=U[query[u][i].first]; ll y=V[query[u][i].first]; if(x!=nodes[depth[x]-1] || y!=nodes[depth[y]-1]) { escaped[query[u][i].second]=true; } } for(auto i:E[u]) { if(i.first!=parent[u]) { DFSexit(i.first); } } nodes.pop_back(); } ll a[N],sum[N]; ll lc[2*N],rc[2*N],nc,root; ll n; void Build(ll &c,ll ss,ll se) { nc++; c=nc; if(ss==se) { sum[c]=0; return; } ll mid=(ss+se)/2; Build(lc[c],ss,mid); Build(rc[c],mid+1,se); sum[c]=min(sum[lc[c]],sum[rc[c]]); } ll Get(ll c,ll ss,ll se,ll qs,ll qe) { if(qs<=ss && se<=qe) { return sum[c]; } if(qe<ss || se<qs) { return inf; } ll mid=(ss+se)/2; return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe)); } void Update(ll c,ll ss,ll se,ll qind,ll qval) { if(ss==se) { a[ss]=qval; sum[c]=qval; //printf("%i %i: %i\n",ss,se,sum[c]); return; } ll mid=(ss+se)/2; if(ss<=qind && qind<=mid) { Update(lc[c],ss,mid,qind,qval); } else { Update(rc[c],mid+1,se,qind,qval); } sum[c]=min(sum[lc[c]],sum[rc[c]]); //printf("%i %i: %i\n",ss,se,sum[c]); } void DFSquery(ll u) { ct++; Update(1,1,n,ct,dp[u]-pref[u]); /*printf("%i: ",u); for(int i=1;i<=n;i++) { printf("%lld ",a[i]); } printf("\n");*/ for(ll i=0;i<query[u].size();i++) { ll x=U[query[u][i].first]; ll y=V[query[u][i].first]; if(escaped[query[u][i].second]==true) { continue; } ll Root=x; if(depth[y]>depth[x]) Root=y; ll mn=Get(1,1,n,depth[Root],ct); res[query[u][i].second]=pref[u]+mn; //printf("%i %i: %lld %i\n",depth[Root],ct,mn,Root); } for(auto i:E[u]) { if(i.first!=parent[u]) { DFSquery(i.first); } } Update(1,1,n,ct,0); ct--; } int main() { ll s,q,e; scanf("%lld%lld%lld%lld",&n,&s,&q,&e); for(ll i=1;i<n;i++) { scanf("%lld%lld%lld",&U[i],&V[i],&W[i]); E[U[i]].push_back({V[i],W[i]}); E[V[i]].push_back({U[i],W[i]}); dp[i]=inf; } dp[n]=inf; for(ll i=1;i<=s;i++) { ll x; scanf("%lld",&x); store[x]=true; } ll ind[n+1],R[n+1]; for(ll i=1;i<=q;i++) { scanf("%lld%lld",&ind[i],&R[i]); query[R[i]].push_back({ind[i],i}); } Build(root,1,n); DFSsetup(e); DFSexit(e); DFSquery(e); /*for(int i=1;i<=n;i++) { printf("%i: %lld\n",i,dp[i]); }*/ for(ll i=1;i<=q;i++) { if(escaped[i]==true) { printf("escaped\n"); } else if(res[i]>=inf) { printf("oo\n"); } else { printf("%lld\n",res[i]); } } return 0; }

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

valley.cpp: In function 'void DFSexit(long long int)':
valley.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(ll i=0;i<query[u].size();i++)
      |             ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void DFSquery(long long int)':
valley.cpp:120:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(ll i=0;i<query[u].size();i++)
      |             ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%lld%lld%lld",&U[i],&V[i],&W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~
valley.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%lld%lld",&ind[i],&R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...