Submission #225915

#TimeUsernameProblemLanguageResultExecution timeMemory
225915frodakcinDreaming (IOI13_dreaming)C++11
0 / 100
61 ms17912 KiB
#include "dreaming.h" #include <vector> #include <algorithm> #include <functional> struct E { public: int n, w; bool operator < (E o) const {return w < o.w || !(o.w < w) && n < o.n;} }; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { std::vector<std::vector<E> > a(N, std::vector<E>(0)); std::vector<bool> vis(N, 0); for(int i = 0;i < M;++i) a[A[i]].push_back({B[i], T[i]}), a[B[i]].push_back({A[i], T[i]}); std::function<E(int, int)> dfs = [&](int n, int p) -> E { vis[n] = 1; E ret = {n, 0}; for(E x : a[n]) if(x.n != p) { E cmp = dfs(x.n, n); cmp.w += x.w; if(ret < cmp) ret = cmp; } return ret; }; std::function<int(int, int, int, int*)> get_dia = [&](int n, int p, int d, int *m) -> int { int md = 0; for(E x : a[n]) if(x.n != p) md = std::max(md, x.w + get_dia(x.n, n, d+x.w, m)); *m = std::min(*m, std::max(md, d)); return md; }; std::vector<int> lis(0); int ldia = 0; for(int i = 1;i <= N;++i) if(!vis[i]) { E t = dfs(i, -1); int val = N*L; int dia = get_dia(t.n, -1, 0, &val); lis.push_back(val); ldia = std::max(ldia, dia); } std::sort(lis.begin(), lis.end(), std::greater<int>()); if(lis.size() == 1) return ldia; else if(lis.size() == 2) return std::max(ldia, lis[0]+lis[1]+L); else return std::max({ldia, lis[0]+lis[1]+L, lis[1]+lis[2]+2*L}); return 42; }

Compilation message (stderr)

dreaming.cpp: In member function 'bool E::operator<(E) const':
dreaming.cpp:11:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  bool operator < (E o) const {return w < o.w || !(o.w < w) && n < o.n;}
                                                 ~~~~~~~~~~~^~~~~~~~~~
#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...