Submission #962934

#TimeUsernameProblemLanguageResultExecution timeMemory
962934vivkostovDreaming (IOI13_dreaming)C++14
0 / 100
1069 ms13300 KiB
#include<bits/stdc++.h> #include "dreaming.h" using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct cell { int to,cost; }; int n,m,l,ma[100005],sma[100005],used[100005],up[100005],otg[100005],A[100005],B[100005],C[100005]; vector<cell>v[100005]; void find_ma(int beg) { used[beg]=1; int w; for(int i=0;i<(int)(v[beg].size());i++) { w=v[beg][i].to; if(!used[w]) { find_ma(w); if(ma[beg]<ma[w]+v[beg][i].cost) { sma[beg]=ma[beg]; ma[beg]=ma[w]+v[beg][i].cost; } else if(sma[beg]<ma[w]+v[beg][i].cost) { sma[beg]=ma[w]+v[beg][i].cost; } } } } void find_up(int beg,int par,int cos) { used[beg]=1; int w; if(ma[par]-cos!=ma[beg]) { up[beg]=max(up[par],ma[par])+cos; } else { up[beg]=max(up[par],sma[par])+cos; } for(int i=0;i<(int)(v[beg].size());i++) { w=v[beg][i].to; if(!used[w]) { find_up(w,beg,v[beg][i].cost); } } } void find_otg(int beg,int lead) { used[beg]=1; int w; for(int i=0;i<(int)(v[beg].size());i++) { w=v[beg][i].to; if(!used[w]) { find_otg(w,lead); } } otg[lead]=min(otg[lead],max(max(ma[beg],sma[beg]),up[beg])); } int travelTime(int n,int m,int l,int A[],int B[],int C[]) //void read() { //cin>>n>>m>>l; cell h; for(int i=1;i<=m;i++) { //cin>>A[i]>>B[i]>>C[i]; A[i]++; B[i]++; h.to=B[i]; h.cost=C[i]; v[A[i]].push_back(h); h.to=A[i]; v[B[i]].push_back(h); } for(int i=1;i<=n;i++) { if(!used[i]) { find_ma(i); } } memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) { if(!used[i]) { find_up(i,0,0); } } memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) { if(!used[i]) { otg[i]=max(max(ma[i],sma[i]),up[i]); find_otg(i,i); } } sort(otg+1,otg+n+1); int aa=0; for(int i=1;i<=n;i++) { aa=max(aa,ma[i]+sma[i]); } if(n!=m+2) { aa=max(aa,2*l+otg[n-2]+otg[n-1]); } aa=max(aa,l+otg[n-1]+otg[n]); cout<<aa<<endl; //return aa; } /*int main() { speed(); read(); return 0; } */

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:126:1: warning: no return statement in function returning non-void [-Wreturn-type]
  126 | }
      | ^
#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...