Submission #110469

#TimeUsernameProblemLanguageResultExecution timeMemory
110469ioilolcomDreaming (IOI13_dreaming)C++14
42 / 100
354 ms27380 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define y second #define x first #define ll long long int #define pb push_back #define pii pair<int,int> using namespace std; const int N=1e5+7; vector<pair<int,int> > adj[N]; bool vis[N]; void dfs(int node,int p,int length,pii &ans){ vis[node]=1; for(auto vertice:adj[node]) { if(vertice.x==p) { continue; } dfs(vertice.x,node,length+vertice.y,ans); } if(length>ans.y) { ans.x=node; ans.y=length; } } bool fn(int s,int e,int p,vector<int> &path){ if(s==e) { return true; } for(auto v:adj[s]) { if(v.x==p) continue; if(fn(v.x,e,s,path)) { path.push_back(v.x); return true; } } return false; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int n=N; int m=M; int l=L; vector<int> radius; map<pair<int,int>,int> cost; 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}); cost[{u,v}]=cost[{v,u}]=w; } int ans=0; for(int i=0; i<n; i++) { if(vis[i]) continue; pii s={-1,-1}; dfs(i,-1,0,s); pii e={-1,-1}; dfs(s.first,-1,0,e); int diameter=e.y; vector<int> path; fn(s.x,e.x,0,path); int sz=(int)path.size(); int rad=diameter; int cur=diameter; ans=max(ans,cur); for(int j=1; j<sz; j++) { cur-=cost[{path[j],path[j-1]}]; rad=min(rad,max(diameter-cur,cur)); } radius.push_back(rad); } int szz=(int)radius.size(); sort(radius.rbegin(),radius.rend()); if(szz>1) { ans=max(ans,radius[0]+radius[1]+l); } if(szz>2) ans=max(ans,radius[1]+radius[2]+2*l); return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:40: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...