제출 #795414

#제출 시각아이디문제언어결과실행 시간메모리
795414jasmin도시들 (IOI15_towns)C++17
25 / 100
14 ms356 KiB
#include "towns.h" #include<bits/stdc++.h> using namespace std; bool balancedSlow(int n, int r, int diameter, map<int, vector<int> >& group, vector<int>& dista){ bool balanced_hub=false; int cntleft=1; for(auto [x, g]: group){ if(max(x, diameter-x)!=r){ //no hub continue; } int cntright = n - cntleft - (int)g.size(); if(cntleft>n/2 || cntright>n/2) continue; vector<bool> vis(n, false); int open = (int)g.size(); bool balanced=true; while(open > n/2){ int v=g.back(); g.pop_back(); if(vis[v]){ continue; } vis[v]=true; int size=1; for(auto u: g){ int d = getDistance(v, u); if(d < dista[v]-x + dista[u]-x){ //same component vis[u]=true; size++; } } if(size > n/2) balanced = false; open -= size; } if(balanced){ balanced_hub = true; break; } cntleft += (int)group.size(); } return balanced_hub; } int hubDistance(int n, int sub) { //find diameter vector<int> dist0(n); int a=1; for(int i=1; i<n; i++){ dist0[i] = getDistance(0, i); if(dist0[i]>dist0[a]){ a=i; } } int b=0; vector<int> dista(n); dista[0] = dist0[a]; for(int i=1; i<n; i++){ if(i==a) continue; dista[i] = getDistance(a, i); if(dista[i] > dista[b]){ b=i; } } vector<int> distb(n); distb[0] = dist0[b]; distb[a] = dista[b]; for(int i=1; i<n; i++){ if(i==a || i==b) continue; distb[i] = getDistance(b, i); } int diameter = dista[b]; //group the leafes vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter; vector<int> ddiam(n); ddiam[a]=ddiam[b]=0; map<int, vector<int> > group; for(int i=0; i<n; i++){ if(i==a || i==b) continue; ddiam[i] = (dista[i]+distb[i] - diameter)/2; dleft[i] = dista[i]-ddiam[i]; group[dleft[i]].push_back(i); } //compute r int r=diameter; for(auto [x, g]: group){ r = min(r, max(x, diameter-x)); } bool balanced = false; if(2<sub){ balanced = balancedSlow(n, r, diameter, group, dista); } if(balanced){ return r; } return -r; }
#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...