Submission #1262234

#TimeUsernameProblemLanguageResultExecution timeMemory
1262234enzyDreaming (IOI13_dreaming)C++20
18 / 100
29 ms12780 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; const int maxn=1e5+10; const int inf=1e9+7; vector<pair<int,int>>v[maxn]; int pai[maxn], resp, val[maxn], at[maxn], cima[maxn], me; pair<int,int> dp[maxn]; void dfs1(int u){ for(pair<int,int> p : v[u]){ int viz=p.first, w=p.second; if(viz==pai[u]) continue; pai[viz]=u; dfs1(viz); if(dp[viz].first+w>dp[u].first){ dp[u].second=dp[u].first; dp[u].first=dp[viz].first+w; }else if(dp[viz].first+w>dp[u].second) dp[u].second=dp[viz].first+w; } resp=max(resp,dp[u].first+dp[u].second); val[u]=at[u]=dp[u].first; } void dfs2(int u){ if(pai[u]!=u){ // se n sou a raiz at[u]=val[u]=max(dp[u].first,cima[u]); } me=min(me,val[u]); for(pair<int,int> p : v[u]){ int viz=p.first, w=p.second; if(viz==pai[u]) continue; if(dp[u].first==dp[viz].first+w) at[u]=max(dp[u].second,cima[u]); else at[u]=max(dp[u].first,cima[u]); cima[viz]=at[u]+w; dfs2(viz); } } int travelTime(int n, int m, int l, int A[], int B[], int T[]){ for(int i=0;i<m;i++){ A[i]++; B[i]++; v[A[i]].push_back({B[i],T[i]}); v[B[i]].push_back({A[i],T[i]}); } vector<int>process; for(int i=1;i<=n;i++){ if(!pai[i]){ me=inf; pai[i]=i; dfs1(i); dfs2(i); if(me==inf) me=0; process.push_back(me); } } sort(process.begin(),process.end()); reverse(process.begin(),process.end()); if(process.size()==1) return process[0]; if(process.size()==2) return process[0]+process[1]+l; if(process.size()>=3) return max(process[0]+process[1]+l,process[1]+process[2]+2*l); }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^
#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...