Submission #840552

#TimeUsernameProblemLanguageResultExecution timeMemory
840552MularstyleDreaming (IOI13_dreaming)C++14
0 / 100
36 ms14104 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define f first #define s second #define pb push_back vector<pii> V[100008]; vector<int> grp[100008]; bool vis1[100008]; bool vis2[100008]; int mxdis[100008]; void ddfs(int prev,int cur,int dis) { mxdis[cur]=max(mxdis[cur],dis); for(auto [w,v]:V[cur]) { if(v!=prev) { ddfs(cur,v,dis+w); } } } void gdfs(int prev,int cur,int g) { vis1[cur]=true; grp[g].pb(cur); for(auto [w,v]:V[cur]) { if(v!=prev) gdfs(cur,v,g); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int u,v,w; for(int i=0;i<M;i++) { u=A[i]; v=B[i]; w=T[i]; V[u].pb({w,v}); V[v].pb({w,u}); } for(int i=0;i<N;i++) { if(vis1[i])continue; gdfs(-1,i,i); } int mx1=-8,mx2=-8,mx3=-8,ans=0; for(int i=0;i<N;i++) { if(grp[i].empty())continue; int prev=N; for(int k=0;k<grp[i].size();k++) { int cur=N; for(auto v:grp[i]) { if(!vis2[v]&&mxdis[v]>=mxdis[prev]&&mxdis[v]>=mxdis[cur]) cur=v; } if(cur==N)/// <3 break; ddfs(N,cur,0); vis2[cur]=true; prev=cur; } int mn=INT_MAX;//shortest from longest for(auto v:grp[i]) { mn=min(mxdis[v],mn); ans=max(ans,mxdis[v]); } if(mn>=mx1) mx3=mx2,mx2=mx1,mx1=mn; else if(mn>=mx2) mx3=mx2,mx2=mn; else if(mn>=mx3) mx3=mn; } ans=max({ans,mx1+mx2+L,mx2+mx3+2*L}); return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'void ddfs(int, int, int)':
dreaming.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [w,v]:V[cur])
      |              ^
dreaming.cpp: In function 'void gdfs(int, int, int)':
dreaming.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [w,v]:V[cur])
      |              ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int k=0;k<grp[i].size();k++)
      |                     ~^~~~~~~~~~~~~~
#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...