Submission #1097136

#TimeUsernameProblemLanguageResultExecution timeMemory
1097136vivkostovDreaming (IOI13_dreaming)C++14
0 / 100
35 ms16220 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; } } } } void find_mid(int beg,int izm) { used[beg]=1; cell w; int ma=0,sma=0; cell ind; 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>sma) { sma=dp[w.to]+w.cost; } } izm=max(izm,sma)+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=0,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=0; 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=0; 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; } void find_mas() { for(int i=0;i<n;i++) { sma=max(sma,dp[lead[i]]+sdp[lead[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)); for(int i=0;i<n;i++) { if(!used[lead[i]])make_dp(lead[i]); } find_max_lead(); if(mind2==-1)return max(dp[mind1],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:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void make_lead(int, int)':
dreaming.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:60:21: warning: 'ind.cell::cost' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     izm=max(izm,sma)+ind.cost;
      |         ~~~~~~~~~~~~^~~~~~~~~
dreaming.cpp:61:14: warning: 'w.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     if(dp[beg]<=max(izm,ma))
      |        ~~~~~~^
dreaming.cpp:55:23: warning: 'ind.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sma)
      |            ~~~~~~~~~~~^~~~~~~~~~~~~~
#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...