Submission #1196185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196185		TimDee	Towns (IOI15_towns)	C++20	35 / 100	10 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];
}

struct DSU {
    vector<int> p,sz;
    DSU(int n) {
        for(int i=0; i<n; ++i) p.pb(i),sz.pb(1);
    }
    int get(int u) {
        return (p[u]==u)?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u), v=get(v);
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        p[v]=u;
        sz[u]+=sz[v];
    }
};

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});
      shuffle(a.begin(), a.end(), rng);
      DSU dsu(n);
      vector<int> ban(n);
      vector<vector<int>> adj(n);
      for(auto&it:a) {
        int u=it.f;
        if (!b.size()) {
          b.pb({1,u}); continue;
        }
        int v=b.back().s;
        int fx = dr[u] - x.f;
        int fy = dr[v] - x.f;
        int fz = ask(u,v);
        //cout<<"> "<<dr[u]<<" "<<dr[v]<<" "<<x.f<<'\n';
        //cout<<"??? "<<u<<' '<<v<<' '<<fx<<' '<<fy<<' '<<fz<<'\n';
        if (fz < fx+fy) {b.back().f++; dsu.uni(u,v);}
        else {
          b.pb({1,u});
          if (b.size()>=2) {
            adj[b[b.size()-1].s].pb(b[b.size()-2].s);
            adj[b[b.size()-2].s].pb(b[b.size()-1].s);
          }
        }
      }
      //for(auto&x:b) cout<<x.f<<','<<x.s<<" "; cout<<'\n';
      sort(b.begin(), b.end());
      vector<int> dp(b.size()+1);
      for(int i=0; i<b.size(); ++i) {
        //cout<<b[i].f<<' '<<b[i].s<<"  "; for(auto&x:adj[b[i].s]) cout<<x<<' '; cout<<'\n';
        dp[i+1] = max(dp[i],b[i].f);
        for(int j=i-1; j>=0; --j) {
          int bad=0;
          for(auto&x:adj[b[i].s]) bad|=x==b[j].s;
          if (bad) continue;
          dp[i+1] = max(dp[i+1], dp[j+1]+b[i].f);
          break;
        }
      }
      //for(int i=0; i<b.size()+1; ++i) cout<<dp[i]<<' '; cout<<'\n';
      if (dp[b.size()] <= n/2) return ans;
      int tot = b.back().f;
      int rt = b.back().s;
      //cout<<"! "<<rt<<' '<<tot<<'\n';
      for(int i=b.size()-2; i>=0; --i) {
        if (dp[i+1] + tot <= n/2) return ans;
        if (tot>=n/2) return -ans;
        //cout<<b[i].f<<' '<<b[i].s<<' '<<tot<<'\n';
        int bad=0;
        for(auto&x:adj[b[i].s]) {
          bad|=dsu.get(x) == dsu.get(rt);
        }
        if (bad) continue;
        int u=b[i].s;
        int fx = dr[u] - x.f;
        int fy = dr[rt] - x.f;
        int fz = ask(u,rt);
        if (fz < fx+fy) {
          dsu.uni(u,rt);
          tot+=b[i].f;
        }
      }
    }
    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