Submission #1097160

#TimeUsernameProblemLanguageResultExecution timeMemory
1097160vivkostovDreaming (IOI13_dreaming)C++14
100 / 100
58 ms22692 KiB
#include<bits/stdc++.h> #define endl '\n' #include"dreaming.h" using namespace std; struct cell { int to,cost; }; int n,m,l,a[200005],b[200005],t[200005],used[200005],lead[200005],dp[200005],sdp[200005],mid,mind1,mind2,mind3,sma; vector<cell>v[200005]; void read() { cin>>n>>m>>l; for(int i=0;i<m;i++) { cin>>a[i]>>b[i]>>t[i]; } } //clear void make_dp(int beg) { used[beg]=1; cell w; for(int i=0;i<v[beg].size();i++) { w=v[beg][i]; if(!used[w.to]) { make_dp(w.to); if(dp[beg]<dp[w.to]+w.cost) { sdp[beg]=dp[beg]; dp[beg]=dp[w.to]+w.cost; } else sdp[beg]=max(sdp[beg],dp[w.to]+w.cost); } } sma=max(sma,dp[beg]+sdp[beg]); } void find_mid(int beg,int izm) { used[beg]=1; cell w; int ma=0,sm=0,oizm=izm; cell ind; ind.cost=0; for(int i=0;i<v[beg].size();i++) { w=v[beg][i]; if(!used[w.to]&&dp[w.to]>ma) { ma=dp[w.to]; ind=w; } } for(int i=0;i<v[beg].size();i++) { w=v[beg][i]; if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sm) { sm=dp[w.to]+w.cost; } } izm=max(izm,sm)+ind.cost; if(max(ma,izm)>=max(dp[beg],oizm)) { mid=beg; } else { find_mid(ind.to,izm); } } void make_lead(int beg,int le) { used[beg]=2; lead[beg]=le; cell w; for(int i=0;i<v[beg].size();i++) { w=v[beg][i]; if(used[w.to]<2) { make_lead(w.to,le); } } } void find_max_lead() { int ma=-1,ind=-1; for(int i=0;i<n;i++) { if(ma<dp[lead[i]]) { ma=dp[lead[i]]; ind=lead[i]; } } mind1=ind; ind=-1; ma=-1; for(int i=0;i<n;i++) { if(lead[i]!=mind1&&ma<dp[lead[i]]) { ma=dp[lead[i]]; ind=lead[i]; } } mind2=ind; ind=-1; ma=-1; for(int i=0;i<n;i++) { if(lead[i]!=mind1&&lead[i]!=mind2&&ma<dp[lead[i]]) { ma=dp[lead[i]]; ind=lead[i]; } } mind3=ind; } int travelTime(int N,int M,int L,int A[],int B[],int T[]) { n=N; m=M; l=L; for(int i=0;i<m;i++) { a[i]=A[i]; b[i]=B[i]; t[i]=T[i]; cell g; g.to=b[i]; g.cost=t[i]; v[a[i]].push_back(g); g.to=a[i]; v[b[i]].push_back(g); } for(int i=0;i<n;i++) { if(!used[i])make_dp(i); } memset(used,0,sizeof(used)); for(int i=0;i<n;i++) { if(!used[i]) { find_mid(i,0); make_lead(i,mid); mid=0; } } memset(used,0,sizeof(used)); memset(dp,0,sizeof(dp)); memset(sdp,0,sizeof(sdp)); for(int i=0;i<n;i++) { if(!used[lead[i]])make_dp(lead[i]); } find_max_lead(); if(mind2==-1)return sma; if(mind3==-1)return max(sma,dp[mind1]+dp[mind2]+l); return max(max(sma,dp[mind1]+dp[mind2]+l),dp[mind2]+dp[mind3]+2*l); } /*int main() { read(); cout<<travelTime(n,m,l,a,b,t)<<endl; return 0; } */

Compilation message (stderr)

dreaming.cpp: In function 'void make_dp(int)':
dreaming.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void make_lead(int, int)':
dreaming.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:59:23: warning: 'ind.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |         if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sm)
      |            ~~~~~~~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...