Submission #842952

#TimeUsernameProblemLanguageResultExecution timeMemory
84295212345678Dreaming (IOI13_dreaming)C++17
100 / 100
93 ms31748 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int nx=1e5+5; int mx[nx], mxr[nx], nxt=0, mx1=INT_MAX, mx2=INT_MAX, ans, cmx, cnt; bool vs[nx]; vector<vector<pair<int, int>>> d(nx); vector<int> b(nx), c; void dfs(int u, int p) { vs[u]=1; c.push_back(u); for (auto [v, w]:d[u]) { if (v==p) continue; dfs(v, u); mx[u]=max(mx[u], mx[v]+w); } } void dfs2(int u, int p) { vector<int> pf(d[u].size()+2), sf(d[u].size()+2); pf[0]=mxr[u]; for (int i=d[u].size()-1; i>=0; i--) { sf[i+1]=sf[i+2]; if (d[u][i].first==p) continue; sf[i+1]=max(sf[i+1], d[u][i].second+mx[d[u][i].first]); } for (int i=0; i<d[u].size(); i++) { pf[i+1]=pf[i]; if (d[u][i].first==p) continue; pf[i+1]=max(pf[i+1], d[u][i].second+mx[d[u][i].first]); mxr[d[u][i].first]=max(pf[i], sf[i+2])+d[u][i].second; } for (auto [v, w]:d[u]) if (v!=p) dfs2(v, u); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { if (N==1) return 0; if (N==2&&M==1) return T[0]; if (N==2) return L; for (int i=0; i<M; i++) d[A[i]].push_back({B[i], T[i]}), d[B[i]].push_back({A[i], T[i]}); for (int i=0; i<N; i++) { if (vs[i]) continue; c.clear(); dfs(i, i); dfs2(i, i); cmx=INT_MAX; for (auto x:c) cmx=min(cmx, max(mx[x], mxr[x])); b[cnt++]=cmx; } for (int i=0; i<N; i++) ans=max(ans, mx[i]+mxr[i]); sort(b.begin(), b.end()); reverse(b.begin(), b.end()); if (cnt==1) return max(ans, b[0]); if (cnt==2) return max(ans, b[0]+b[1]+L); return max(ans, max(b[0]+L+b[1], b[1]+2*L+b[2])); }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i=0; i<d[u].size(); i++)
      |                   ~^~~~~~~~~~~~
#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...