제출 #235642

#제출 시각아이디문제언어결과실행 시간메모리
235642bharat2002Valley (BOI19_valley)C++14
23 / 100
315 ms51064 KiB
/*input 10 2 5 4 7 2 3 4 8 3 9 10 1 6 7 3 9 2 3 10 1 2 8 2 2 5 2 1 3 8 2 8 7 2 1 1 5 8 4 6 2 7 7 */ #include<bits/stdc++.h> using namespace std; const int N=1e5 + 100; const int mod=1e9 + 7; const int N2=20; #define int long long const int inf=1e18; #define pii pair<int, int> #define f first #define s second #define mp make_pair #define FOR(i, n) for(int i=1;i<=n;i++) #define TRACE(x) cerr << #x << " = " << x << endl //Trace prints the name of the variable and the value. int q, start[N], fin[N], dp[N], pv[N][N2], p[N][N2], depth[N], n, e, s;vector< pii > adjlist[N];bool is[N];int ct; void dfs(int i) { dp[i]=inf;start[i]=ct++; for(auto j:adjlist[i]) { if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=i; p[j.f][0]=i; dfs(j.f); dp[i]=min(dp[i], dp[j.f] + 2*depth[j.f] - 2*depth[i]); } if(is[i]) dp[i]=-depth[i]; fin[i]=ct-1; } pii edges[N]; void solve() { cin>>n>>s>>q>>e;ct=1; for(int i=1;i<=n;i++) { is[i]=0;start[i]=-1; } for(int i=1;i<n;i++) { int u, v, w;cin>>u>>v>>w;edges[i]=(mp(u, v)); adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w)); } while(s--) { int v;cin>>v;is[v]=1; } depth[e]=0; dfs(e); for(int i=1;i<=n;i++) pv[i][0]=dp[p[i][0]]; for(int j=1;j<N2;j++) for(int i=1;i<=n;i++) { p[i][j]=p[p[i][j-1]][j-1]; pv[i][j]=min(pv[i][j-1], pv[p[i][j-1]][j-1]);} while(q--) { int ind, r;cin>>ind>>r; int u=edges[ind].f, v=edges[ind].s; if(start[u]>start[v]) swap(u, v); if(start[v]<=start[r]&&fin[v]>=fin[r]) { int diff=depth[r]-depth[v];int ans=dp[r];int add=depth[r]; for(int i=N2-1;i>=0;i--) { if((1<<i)<=diff) {ans=min(ans, pv[r][i]);r=p[r][i];diff-=(1<<i);} } if(ans>=inf) cout<<"oo\n"; else cout<<ans+add<<endl; } else cout<<"escaped\n"; } /* for(int i=1;i<=n;i++) { cout<<i<<": "<<dp[i]<<endl; }*/ } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int t=1; while(t--) { solve(); } }

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

valley.cpp: In function 'void dfs(long long int)':
valley.cpp:40:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=i;
   ^~
valley.cpp:40:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(start[j.f]!=-1) continue;depth[j.f]=depth[i]+j.s;dp[j.f]=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...