Submission #110124

#TimeUsernameProblemLanguageResultExecution timeMemory
110124ioilolcomDreaming (IOI13_dreaming)C++14
0 / 100
80 ms13176 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define s second #define f first #define ll long long int #define pb push_back using namespace std; const int N=1e5+7; vector<pair<int,int> > adj[N]; bool vis[N]; int d[N]; int par[N]; int c[N]; int mx; int start=-1,tok=-1; void dfs(int u,int p,int l){ vis[u]=1; for(auto v:adj[u]) { if(v.f==p) { continue; } dfs(v.f,u,l+v.s); } if(l>mx) { mx=l; start=u; } } void dfs2(int u,int p,int l){ vis[u]=1; for(auto v:adj[u]) { if(v.f==p) { continue; } par[v.f]=u; d[v.f]=d[u]+v.s; dfs2(v.f,u,l+v.s); } if(l>mx) { mx=l; tok=u; } } int radius(int u,int p){ //memset(par,-1,sizeof par); mx=0; start=-1; tok=-1; dfs(u,p,0); mx=0; if(start==-1) { return 0; } dfs2(start,p,0); int diameter=mx; int ans=1e9; for(int u=tok; u!=start; u=par[u]) { //cout<<u<<" "<<d[u]<<endl; ans=min(ans,max(diameter-d[u],d[u])); } // cout<<ans<<endl; return ans; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int n=N; int m=M; int l=L; for(int i=0; i<M; i++) { int u=A[i]; int v=B[i]; int w=T[i]; adj[u].pb({v,w}); adj[v].pb({u,w}); } int cnt=1; for(int i=0; i<n; i++) { if(!vis[i]) { vis[i]=1; //dfs(i,-1,0); c[cnt]=radius(i,-1); cnt++; } } int mx1=0; int mx2=0; for(int i=1; i<cnt; i++) { if(c[i]>mx1) { mx2=mx1; mx1=c[i]; } else if(c[i]>mx2) { mx2=c[i]; } } int lol=mx1+mx2+l; return lol; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:6: warning: unused variable 'm' [-Wunused-variable]
  int m=M;
      ^
#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...