oj.uz

Submission #553969

# Submission time Handle Problem Language Result Execution time Memory
553969 2022-04-27T12:49:57 Z cadmiumsky Towns (IOI15_towns) C++14
100 / 100
 16 ms 980 KB 
#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);
  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) {
    //return;z
    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) {
  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;
  }
  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);
  cleaf.resize(cnt);
  int lside = 1, rside = 0;
  for(int i = 0; i < N; i++) {
    if(i == D1 || i == D2)
      continue;
    int x = getdist(D1, root, i);
    if(cnt == 2) {
      if(x < mpoint)
        lside++;
      else if(x == mpoint)
        cleaf[0].push_back(i);
      else if(x == getdist(D1, D2) - mpoint)
        cleaf[1].push_back(i);
      else
        rside++;
    }
    else if(x == mpoint)
      cleaf[0].push_back(i);
    else if(x > mpoint)
      rside++;
    else
      lside++;
  }
 if(lside > N / 2)
    return -R;
  if(rside == 0)
    cleaf.back().push_back(D2);
  else
    rside++;
  if(rside > N /2)
    return -R;
  d1c = mpoint;
  if(cleaf.size() == 2) {
    if(cleaf[0].size() < cleaf[1].size())
      d1c = getdist(D1, D2) - mpoint, swap(cleaf[0], cleaf[1]);
    
  }
  sort(cleaf[0].begin(), cleaf[0].end());
  return divine(cleaf[0]) * R;
}

Compilation message

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:78:36: warning: unused parameter 'susb' [-Wunused-parameter]
   78 | int hubDistance(int sussussus, int susb) {
      |                                ~~~~^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 980 KB Output is correct
2 Correct 11 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 14 ms 892 KB Output is correct
5 Correct 16 ms 828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 436 KB Output is correct
2 Correct 14 ms 832 KB Output is correct
3 Correct 15 ms 468 KB Output is correct
4 Correct 14 ms 852 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 852 KB Output is correct
2 Correct 14 ms 832 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 13 ms 824 KB Output is correct
3 Correct 14 ms 852 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 440 KB Output is correct
2 Correct 14 ms 852 KB Output is correct
3 Correct 14 ms 852 KB Output is correct