Submission #1013349

#TimeUsernameProblemLanguageResultExecution timeMemory
1013349LuvidiDreaming (IOI13_dreaming)C++17
18 / 100
32 ms16168 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int,int> const int maxn=1e5; vector<pii> adj[maxn]; int d[maxn][2],d2[maxn],d3[maxn]; bool vis[maxn]; void dfs(int v,int p){ vis[v]=1; vector<int> z; for(auto [i,x]:adj[v])if(i!=p){ dfs(i,v); z.pb(d[i][0]+x); } sort(z.rbegin(),z.rend()); for(int i=0;i<z.size()&&i<2;i++)d[v][i]=z[i]; } void dfs2(int v,int p,int r){ d3[r]=min(d3[r],max(d[v][0],d2[v])); for(auto [i,x]:adj[v])if(i!=p){ if(d[v][0]==d[i][0]+x){ d2[i]=x+max(d[v][1],d2[v]); }else{ d2[i]=x+max(d[v][0],d2[v]); } dfs2(i,v,r); } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { for(int i=0;i<m;i++){ adj[a[i]].pb({b[i],t[i]}); adj[b[i]].pb({a[i],t[i]}); } vector<int> v; for(int i=0;i<n;i++){ if(!vis[i]){ dfs(i,-1); d3[i]=1e9; dfs2(i,-1,i); v.pb(d3[i]); } } sort(v.rbegin(),v.rend()); if(v.size()==1){ return v[0]; }else if(v.size()==2){ return v[0]+v[1]+l; }else{ return max(v[0],v[2]+l)+v[1]+l; } }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<z.size()&&i<2;i++)d[v][i]=z[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...