Submission #1196630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196630		TimDee	Towns (IOI15_towns)	C++20	35 / 100	17 ms	328 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second

int mem[111][111];

int ask(int i, int j) {
  if (i==j) return 0;
  if (mem[i][j]) return mem[i][j];
  mem[i][j] = mem[j][i] = getDistance(i, j);
  return mem[i][j];
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int hubDistance(int n, int ilyashevchenko1love) {
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) mem[i][j]=0;

  vector<int> d0(n), dr(n);
  int r=1;
  for(int i=1; i<n; ++i) {
    d0[i] = ask(0,i);
    if (d0[i] > d0[r]) r=i;
  }
  int l=0;
  for(int i=0; i<n; ++i) {
    dr[i] = ask(r,i);
    if (dr[i] > dr[l]) l=i;
  }
  int diam = dr[l];
  map<int,vector<int>> m;
  if (l==0) {
    for(int i=0; i<n; ++i) {
      int z = (d0[i]+dr[i]-diam)>>1;
      m[dr[i]-z].pb(i);
    }
  } else {
    int z0 = (d0[l]+d0[r]-diam)>>1;
    int dr0 = dr[0]-z0;
    m[dr0].pb(0);
    for(int i=1; i<n; ++i) {
      if (i==l) {
        m[diam].pb(i); continue;
      }
      if (i==r) {
        m[0].pb(i); continue;
      }
      int z = (d0[i] + dr[i] - d0[r])>>1;
      if (dr[i]-z < dr0) {
        m[dr[i]-z].pb(i);
      } else if (dr[i]-z == dr0) {
        m[dr0].pb(i);
      } else {
        m[dr0].pb(i);
      }
    }
  }
  int ans=diam;
  for(auto&x:m) {
    ans=min(ans,max(x.f,diam-x.f));
  }
  int left=0,right=n;
  for(auto&x:m) {
    int z = max(x.f, diam-x.f);
    int sz = x.s.size();
    right-=sz;
    if (z==ans) if (max({left,right,sz}) <= n/2) return ans;
    left+=sz;
  }
  left=0,right=n;
  for(auto&x:m) {
    int z = max(x.f, diam-x.f);
    int sz = x.s.size();
    right-=sz;
    if (z==ans) if (max(left,right) <= n/2) {
      vector<pi> a,b;
      for(auto&v:x.s) a.pb({v,1});

      while (a.size() > 1) {
        vector<pi> c;
        shuffle(a.begin(), a.end(), rng);
        for(int i=0; i+1<a.size(); i+=2) {
          int u=a[i].f, v=a[i+1].f;
          int fx = dr[u]-x.f;
          int fy = dr[v]-x.f;
          int fz = ask(u,v);
          if (fz < fx+fy) {
            c.pb({u,a[i].s+a[i+1].s});
          } else {
            b.pb(a[i]);
            b.pb(a[i+1]);
          }
        }
        if (a.size()&1) b.pb(a.back());
        a=c;
      }
      if (!a.size()) return ans;
      int rt = a[0].f;
      int tot = a[0].s;
      //cout<<"? "<<tot<<' '<<rt<<'\n';
      for(auto&it:b) {
        int fx = dr[it.f]-x.f;
        int fy = dr[rt]-x.f;
        int fz = ask(it.f,rt);
        if (fz < fx+fy) tot+=it.s;
        if (tot>n/2) return -ans;
      }
      return ans;
    }
    left+=sz;
  }
  return -ans;

}

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