Submission #126856

#TimeUsernameProblemLanguageResultExecution timeMemory
126856Bench0310Dreaming (IOI13_dreaming)C++17
0 / 100
1070 ms16752 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; const int N=100005; const int inf=1000000000; vector<pair<int,int>> v[N]; vector<bool> vis(N,0); vector<int> diameter(N,0); vector<int> center(N,0); vector<int> path; pair<int,int> get_last(int a) { vector<int> dist(N,-1); dist[a]=0; queue<int> q; q.push(a); int last=a; while(!q.empty()) { int e=q.front(); q.pop(); vis[e]=1; for(pair<int,int> p:v[e]) { int to=p.first; if(dist[to]!=-1) continue; dist[to]=dist[e]+p.second; q.push(to); if(dist[to]>dist[last]) last=to; } } return make_pair(last,dist[last]); } bool get_path(int a,int p,int b) { if(a==b) return 1; for(pair<int,int> temp:v[a]) { int to=temp.first; if(to==p) continue; if(get_path(to,a,b)) { path.push_back(temp.second); return 1; } } return 0; } void get_center(int a,int id) { int one,two,len; tie(one,ignore)=get_last(a); tie(two,len)=get_last(one); diameter[id]=len; path.clear(); get_path(one,-1,two); int best=diameter[id]; int sum=0; for(int i=0;i<(int)path.size();i++) { sum+=path[i]; best=min(best,max(sum,diameter[id]-sum)); } center[id]=best; } int solve(int n,int l) { int id=0; for(int i=0;i<n;i++) if(vis[i]==0) get_center(i,id++); int res=0; vector<pair<int,int>> root; for(int i=0;i<id;i++) { res=max(res,diameter[id]); root.push_back(make_pair(center[i],i)); } sort(root.begin(),root.end(),greater<pair<int,int>>()); if(id>1) res=max(res,root[0].first+l+root[1].first); if(id>2) res=max(res,root[1].first+2*l+root[2].first); return res; } int travelTime(int n,int m,int l,int a[],int b[],int t[]) { for(int i=0;i<m;i++) { v[a[i]].push_back(make_pair(b[i],t[i])); v[b[i]].push_back(make_pair(a[i],t[i])); } return solve(n,l); } /*int main() { int n,m,l; scanf("%d%d%d",&n,&m,&l); for(int i=0;i<m;i++) { int a,b,t; scanf("%d%d%d",&a,&b,&t); v[a].push_back(make_pair(b,t)); v[b].push_back(make_pair(a,t)); } printf("%d\n",solve(n,l)); return 0; }*/
#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...