Submission #1028361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028361		huutuan	Towns (IOI15_towns)	C++14	0 / 100	18 ms	656 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>

using namespace std;

int dd[200][200];

mt19937 rng(69420);

int GetDistance(int u, int v){
   if (u==v) return 0;
   if (dd[u][v]) return dd[u][v];
   int tmp=getDistance(u, v);
   dd[u][v]=tmp; dd[v][u]=tmp;
   return tmp;
}

int hubDistance(int N, int sub) {
   memset(dd, 0, sizeof dd);
   int u=0, dis=0;
   for (int i=1; i<N; ++i){
      int d=GetDistance(0, i);
      if (d>dis){
         dis=d;
         u=i;
      }
   }
   dis=0;
   int v=u;
   for (int i=0; i<N; ++i) if (i!=u){
      int d=GetDistance(u, i);
      if (d>dis){
         dis=d;
         v=i;
      }
   }
   int ans=1e9;
   vector<pair<int, int>> vv;
   for (int i=0; i<N; ++i) if (i!=u && i!=v){
      int d0=(GetDistance(0, i)+GetDistance(0, u)-GetDistance(u, i))/2, du=GetDistance(0, u)-d0;
      ans=min(ans, max(du, dis-du));
      vv.emplace_back(du, dis-du);
   }
   if (sub<=2) return ans;
   sort(vv.begin(), vv.end());
   vv.resize(unique(vv.begin(), vv.end())-vv.begin());
   int cnt=0;
   for (auto &ii:vv) if (max(ii.first, ii.second)==ans) ++cnt;
   int mx=N/2;
   for (auto &ii:vv) if (max(ii.first, ii.second)==ans){
      int szl=0, szr=0;
      vector<int> child(N);
      iota(child.begin(), child.end(), 0);
      vector<int> is_valid(N);
      auto check=[&](int x, int y) -> bool {
         if (!is_valid[x] || !is_valid[y]) return false;
         return GetDistance(u, x)+GetDistance(u, y)-ii.first*2-GetDistance(x, y)>0;
      };
      for (int i=0; i<N; ++i){
         int d0=(GetDistance(0, i)+GetDistance(0, u)-GetDistance(u, i))/2, du=GetDistance(0, u)-d0;
         if (du<ii.first) ++szl;
         else if (du>ii.first) ++szr;
         else is_valid[i]=1;
      }
      if (szl>mx || szr>mx) continue;
      vector<int> v1, v2;
      for (int i:child){
         if (v1.size() && check(v1.back(), i)){
            v2.push_back(i);
         }else{
            v1.push_back(i);
            if (v2.size()) v1.push_back(v2.back()), v2.pop_back();
         }
      }
      bool ff=0;
      if (v1.size()){
         int t=v1.back(); v1.pop_back();
         while (v1.size()){
            if (check(v1.back(), t)){
               if ((int)v1.size()==1) v2.push_back(v1.back()), v1.pop_back();
               else v1.pop_back(), v1.pop_back();
            }else{
               if (v2.empty()){
                  ff=1;
                  break;
               }
               v2.pop_back();
               v1.pop_back();
            }
         }
      }else ff=1;
      if (v2.size()) ff=1;
      if (ff) return ans;
   }
   return -ans;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39