Submission #1029569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029569		huutuan	Towns (IOI15_towns)	C++14	100 / 100	11 ms	1184 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;
      }
   }
   pair<int, vector<int>> ans={1e9, {}};
   vector<int> vv;
   int d0v=(GetDistance(0, v)+GetDistance(0, u)-GetDistance(u, v))/2, duv=GetDistance(0, u)-d0v;
   int dvv=GetDistance(v, u)-duv;
   for (int i=0; i<N; ++i) if (i!=u && i!=0){
      int d0=(GetDistance(0, i)+GetDistance(0, u)-GetDistance(u, i))/2, du=GetDistance(0, u)-d0;
      if (du<=duv){
         int val=max(du, duv-du+dvv);
         if (ans.first>val) ans={val, {du}};
         else if (ans.first==val) ans.second.push_back(du);
      }
      vv.emplace_back(du);
   }
   if (sub<=2) return ans.first;
   sort(vv.begin(), vv.end());
   vv.resize(unique(vv.begin(), vv.end())-vv.begin());
   int mx=N/2;
   for (auto &ii:vv) if (find(ans.second.begin(), ans.second.end(), ii)!=ans.second.end()){
      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*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) ++szl;
         else if (du>ii) ++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();
         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.first;
   }
   return -ans.first;
}

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