Submission #553768

#	Time	Username	Problem	Language	Result	Execution time	Memory
553768		cadmiumsky	Towns (IOI15_towns)	C++14	25 / 100	16 ms	980 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int N;
const int nmax = 110;
int precalc[nmax][nmax];
int getdist(int l, int r) {
  if(l == r)
    return 0;
  if(l > r) 
    swap(l, r);
  if(precalc[l][r] == -1)
    return precalc[l][r] = getDistance(l, r);
  return precalc[l][r];
}

int getdist(int x, int l, int r) { // distanta de la x la lantul [L, R]
  return (getdist(x, l) + getdist(x, r) - getdist(l, r)) / 2;
}
int d1c;
int D1 = 0, D2 = 0, root = 0;
bool islca(int x, int y) {
  bool ok = getdist(D1, x) + getdist(D1, y) - d1c * 2 == getdist(x, y);
  //if(!ok)
    //cerr << "> " << x << ' ' << y << '\n';
  return ok;
}

namespace DSU {
  int dsu[nmax];
  void init(int n) {
    for(int i = 0; i <= n; i++)
      dsu[i] = i;
  }
  int father(int x) { return (dsu[x] == x? x : father(dsu[x] = father(dsu[dsu[x]]))); }
  void unite(int x, int y) {
    x = father(x);
    y = father(y);
    dsu[y] = x;
  }
  bool check(int x, int y) {return father(x) == father(y); }
};

int divide(vector<int> v) {
  if(v.size() == 0)
    return -1;
  if(v.size() == 1)
    return v[0];
  int safe = -1; 
  if(v.size() % 2 == 1)
    safe = v.back(), v.pop_back();
  vector<int> nova;
  for(int i = 0; i < v.size(); i += 2)
    if(!islca(v[i], v[i + 1]))
      nova.push_back(v[i]), DSU::unite(v[i], v[i + 1]);
  int their = divide(nova);
  if(their == -1)
    return safe;
  return their;
}
int check(int cand, vector<int> v) {
  int cnt = 0;
  for(auto x : v)
    if(!islca(cand, DSU::father(x)))
      cnt++;
  if(cnt > N /2)
    return -1;
  return 1;
}
int divine(vector<int> v) {
  //for(auto x : v)
    //cerr << x << ' ';
  //cerr << '\n';
  int cand = divide(v);
  if(cand == -1)
    return -1;
  else
    return check(cand, v);
}

int hubDistance(int sussussus, int susb) {
  N = sussussus;
  DSU::init(N);
  for(int i = 0; i < N; i++)  
    for(int j = 0; j < N; j++)
      precalc[i][j] = -1;
  // root random?
  for(int i = 1; i < N; i++) {
    if(getdist(root, i) > getdist(root, D1))
      D1 = i;
    //cerr << i << '\t' << getdist(root, i) << ' ' << getdist(root, D1)<< '\n';
  }
  //cerr << D1 << '\n';
  D2 = D1;
  for(int i = 0; i < N; i++) {
    if(getdist(i, D1) > getdist(D2, D1))
      D2 = i;
  }
  // D1, 0 o sa fie un lant aproximativ diametral, macar trece centrul
  vector<int> pdist;
  for(int i = 0; i < N; i++) {
    pdist.push_back(getdist(D1, root, i));
  }
  sort(pdist.begin(), pdist.end());
  pdist.resize(distance(pdist.begin(), unique(pdist.begin(), pdist.end())));
  vector< vector<int> > cleaf;
  int R = getdist(D1, D2), cnt = 0, mpoint = R;
  for(auto x : pdist)
    R = min(R, max(x, getdist(D1, D2) - x));
  for(auto x : pdist)
    if(max(x, getdist(D1, D2) - x) == R)
      cnt++, mpoint = min(mpoint, x);
       //cerr << x << '\n';
  cleaf.resize(cnt);
  //cerr << mpoint << '\n';
  int lside = 1;
  for(int i = 0; i < N; i++) {
    if(i == D1 || i == D2)
      continue;
    int x = getdist(D1, root, i);
    if(cnt == 2) {
      //cerr << x << ' ' << i << "=> ";
      if(x < mpoint)
        lside++;
      if(x == mpoint)
        cleaf[0].push_back(i);
      else
        cleaf[1].push_back(i);
    }
    else if(x >= mpoint)
      cleaf[0].push_back(i);
    else
      lside++;
  }
  //cerr << cnt << ' ' << lside << ' ' << R << ' ' << N / 2 << ' ' << getdist(D1, root) - getdist(root, D1, D2)<< '\n';
  if(lside > N / 2)
    return -R;
  cleaf.back().push_back(D2);
  if(cleaf.size() == 2) {
    cleaf[0].push_back(D1);
    //cerr <<"> "<< cleaf[0].size() << ' ' << cleaf[1].size() << ' ' << D1 << ' ' << D2 << '\n';
    //for(auto x : cleaf[0])
      //cerr << x << ' ';
    //cerr << '\n';
    //for(auto x : cleaf[1])
      //cerr << x << ' ';
    //cerr << '\n';
    if(cleaf[0].size() < cleaf[1].size())
      swap(cleaf[0], cleaf[1]);
    //swap()
  }
  sort(cleaf[0].begin(), cleaf[0].end());
  d1c = getdist(D1, D2) - getdist(D2, cleaf[0][0] , D1);
  return divine(cleaf[0]) * R;
}

Compilation message (stderr)

towns.cpp: In function 'int divide(std::vector<int>)':
towns.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i = 0; i < v.size(); i += 2)
      |                  ~~^~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:36: warning: unused parameter 'susb' [-Wunused-parameter]
   81 | int hubDistance(int sussussus, int susb) {
      |                                ~~~~^~~~

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