Submission #827858

#	Time	Username	Problem	Language	Result	Execution time	Memory
827858		I_Love_EliskaM_	Towns (IOI15_towns)	C++17	35 / 100	13 ms	360 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9+9;
     
int p1(int n) {
  vector<int> a(n), b(n), c(n);
  int f=0;
  forn(i,n) {
    a[i]=getDistance(0,i);
    if (a[i]>a[f]) f=i;
  }
  int s=0;
  forn(i,n) {
    b[i]=getDistance(f,i);
    if (b[i]>b[s]) s=i;
  }
  forn(i,n) {
    c[i]=getDistance(s,i);
  }

  set<int> st;

  vector<int> d(n);
  map<int,vector<int>> ok;

  forn(i,n) {
    if (i==f || i==s) continue;
    int x=b[i], y=c[i], z=b[s];
    int A=(x-y+z)/2;
    d[i]=x-A;
    st.insert(A);
    ok[A].pb(i);
  }

  int ans=inf;
  for(auto&x:st) {
    int y=b[s]-x;
    ans=min(ans,max(x,y));
  }
  int l=1;
  for(auto&x:st) {
    int y=b[s]-x;
    if (max(x,y)!=ans) {
      l+=ok[x].size();
      continue;
    }
    int r=n-ok[x].size()-l;
    if (max(l,r)>n/2) continue;
    int t=ok[x].size();
    if (t<=n/2) return ans;
  }

  return -ans;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int p5(int n) {
  vector<int> a(n), b(n), c(n);
  int f=0;
  forn(i,n) {
    a[i]=getDistance(0,i);
    if (a[i]>a[f]) f=i;
  }
  int s=0;
  forn(i,n) {
    b[i]=getDistance(f,i);
    if (b[i]>b[s]) s=i;
  }
  forn(i,n) {
    c[i]=getDistance(s,i);
  }

  set<int> st;

  vector<int> d(n);
  map<int,vector<int>> ok;

  forn(i,n) {
    if (i==f || i==s) continue;
    int x=b[i], y=c[i], z=b[s];
    int A=(x-y+z)/2;
    d[i]=x-A;
    st.insert(A);
    ok[A].pb(i);
  }

  int ans=inf;
  for(auto&x:st) {
    int y=b[s]-x;
    ans=min(ans,max(x,y));
  }
  int l=1;
  for(auto&x:st) {
    int y=b[s]-x;
    if (max(x,y)!=ans) {
      l+=ok[x].size();
      continue;
    }
    int r=n-ok[x].size()-l;
    if (max(l,r)>n/2) continue;
    int t=ok[x].size();
    if (t<=n/2) return ans;
    vector<pi> a,b;
    for(auto&v:ok[x]) a.pb({v,1});
    while (a.size()>1) {
      shuffle(all(a),rng);
      int k = a.size();
      for (int i=0; i+1<a.size(); i+=2) {
        int z = getDistance(a[i].f,a[i+1].f);
        int x = d[a[i].f], y = d[a[i+1].f];
        if (z==x+y) {
          if (a[i].s > a[i+1].s) b.pb(a[i]);
          else b.pb(a[i+1]);
          continue;
        }
        b.pb({a[i].f,a[i].s+a[i+1].s});
      }
      if (k&1) b.pb(a.back());
      a=b;
      b.clear();
    }
    int u=a[0].f;
    int sz=0;
    for(auto&v:ok[x]) {
      int z = getDistance(u,v);
      int x = c[u], y = c[v];
      if (z<x+y) ++sz;
    }
    if (sz<=n/2) return ans;
    l+=ok[x].size();
  }

  return -ans;
}

int hubDistance(int n, int sub) {
  if (sub<=2 || sub==4) return p1(n);
  if (sub>=3) return p5(n);
  return 0;
}

Compilation message (stderr)

towns.cpp: In function 'int p1(int)':
towns.cpp:51:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |       l+=ok[x].size();
      |                     ^
towns.cpp:54:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   54 |     int r=n-ok[x].size()-l;
      |           ~~~~~~~~~~~~~~^~
towns.cpp:56:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |     int t=ok[x].size();
      |           ~~~~~~~~~~^~
towns.cpp: In function 'int p5(int)':
towns.cpp:103:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |       l+=ok[x].size();
      |                     ^
towns.cpp:106:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  106 |     int r=n-ok[x].size()-l;
      |           ~~~~~~~~~~~~~~^~
towns.cpp:108:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  108 |     int t=ok[x].size();
      |           ~~~~~~~~~~^~
towns.cpp:110:16: warning: declaration of 'a' shadows a previous local [-Wshadow]
  110 |     vector<pi> a,b;
      |                ^
towns.cpp:65:15: note: shadowed declaration is here
   65 |   vector<int> a(n), b(n), c(n);
      |               ^
towns.cpp:110:18: warning: declaration of 'b' shadows a previous local [-Wshadow]
  110 |     vector<pi> a,b;
      |                  ^
towns.cpp:65:21: note: shadowed declaration is here
   65 |   vector<int> a(n), b(n), c(n);
      |                     ^
towns.cpp:114:21: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  114 |       int k = a.size();
      |               ~~~~~~^~
towns.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       for (int i=0; i+1<a.size(); i+=2) {
      |                     ~~~^~~~~~~~~
towns.cpp:117:13: warning: declaration of 'x' shadows a previous local [-Wshadow]
  117 |         int x = d[a[i].f], y = d[a[i+1].f];
      |             ^
towns.cpp:100:12: note: shadowed declaration is here
  100 |   for(auto&x:st) {
      |            ^
towns.cpp:117:28: warning: declaration of 'y' shadows a previous local [-Wshadow]
  117 |         int x = d[a[i].f], y = d[a[i+1].f];
      |                            ^
towns.cpp:101:9: note: shadowed declaration is here
  101 |     int y=b[s]-x;
      |         ^
towns.cpp:133:11: warning: declaration of 'x' shadows a previous local [-Wshadow]
  133 |       int x = c[u], y = c[v];
      |           ^
towns.cpp:100:12: note: shadowed declaration is here
  100 |   for(auto&x:st) {
      |            ^
towns.cpp:133:21: warning: declaration of 'y' shadows a previous local [-Wshadow]
  133 |       int x = c[u], y = c[v];
      |                     ^
towns.cpp:101:9: note: shadowed declaration is here
  101 |     int y=b[s]-x;
      |         ^
towns.cpp:137:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  137 |     l+=ok[x].size();
      |                   ^

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