Submission #1097155

#TimeUsernameProblemLanguageResultExecution timeMemory
1097155vivkostovDreaming (IOI13_dreaming)C++14
18 / 100
38 ms15840 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]; } } 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; 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(dp[beg]<=max(izm,ma)) { mid=beg; } else { find_mid(w.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 get_sma(int beg,int par) { cell w; for(int i=0;i<v[beg].size();i++) { w=v[beg][i]; if(w.to!=par)return get_sma(w.to,beg)+w.cost; } return 0; } void find_sma() { for(int i=0;i<n;i++) { if(v[i].size()<2)sma=max(sma,get_sma(i,i)); } } 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(); find_sma(); 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:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void make_lead(int, int)':
dreaming.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int get_sma(int, int)':
dreaming.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:64:14: warning: 'w.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     if(dp[beg]<=max(izm,ma))
      |        ~~~~~~^
dreaming.cpp:58:23: warning: 'ind.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |         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...