Submission #1063834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063834		Hanksburger	Towns (IOI15_towns)	C++17	100 / 100	14 ms	1116 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
long long d[115][115], a[115], b[115];
vector<long long> vec, cur, tmp;
int hubDistance(int n, int sub)
{
    long long ind1=0, ind2=0;
    d[0][0]=0;
    for (long long i=1; i<n; i++)
    {
        d[0][i]=getDistance(0, i);
        if (d[0][ind1]<d[0][i])
            ind1=i;
    }
    d[ind1][0]=d[0][ind1];
    d[ind1][ind1]=0;
    for (long long i=1; i<n; i++)
    {
        if (i==ind1)
            continue;
        d[ind1][i]=getDistance(ind1, i);
        if (d[ind1][ind2]<d[ind1][i])
            ind2=i;
    }
    long long diameter=d[ind1][ind2], mx=-1, mn=1e18, val, cnt1=0, cnt2=0;
    for (long long i=0; i<n; i++)
    {
        a[i]=(d[ind1][0]+d[ind1][i]-d[0][i])/2;
        if (a[i]*2<=diameter)
            mx=max(mx, a[i]);
        else
            mn=min(mn, a[i]);
    }
    if (mx+mn<diameter)
        val=mn;
    else if (mx+mn>diameter)
        val=mx;
    else
    {
        long long cnt=0;
        for (long long i=0; i<n; i++)
            if (a[i]<=mx)
                cnt++;
        if (cnt*2<=n)
            val=mn;
        else
            val=mx;
    }
    for (long long i=0; i<n; i++)
    {
        if (a[i]<val)
            cnt1++;
        else if (a[i]>val)
            cnt2++;
    }
    if (cnt1*2>n || cnt2*2>n)
        return -max(val, diameter-val);
    //cout << '\n';
    //cout << "diameter " << diameter << '\n';
    //cout << "mx " << mx << '\n';
    //cout << "mn " << mn << '\n';
    //cout << "val " << val << '\n';
    vec.clear();
    cur.clear();
    tmp.clear();
    for (long long i=0; i<n; i++)
    {
        if (a[i]==val)
        {
            vec.push_back(i);
            cur.push_back(i);
            //cout << "push " << i << '\n';
            b[i]=0;
        }
    }
    long long tie=-1, cnt=0;
    for (long long i=0;; i++)
    {
        //cout << "round starts\n";
        for (long long j=0; j+1<cur.size(); j+=2)
        {
            long long res=getDistance(cur[j], cur[j+1]);
            if (res<d[ind1][cur[j]]-a[cur[j]]+d[ind1][cur[j+1]]-a[cur[j+1]])
            {
                tmp.push_back(cur[j]);
                b[cur[j]]++;
                b[cur[j+1]]=-1;
                //cout << "push " << cur[j] << '\n';
            }
        }
        if (cur.size()%2==1)
            tie=cur.back();
        if (tmp.empty())
            break;
        cur=tmp;
        tmp.clear();
    }
    //cout << "tie " << tie << '\n';
    if (tie==-1)
        return max(val, diameter-val);
    for (long long i=0; i<vec.size(); i++)
    {
        if (b[vec[i]]==-1)
            continue;
        //cout << "vec " << i << " = " << vec[i] << '\n';
        //cout << "b vec " << i << " = " << b[vec[i]] << '\n';
        if (vec[i]==tie)
        {
            cnt+=(1<<b[vec[i]]);
            continue;
        }
        long long res=getDistance(vec[i], tie);
        if (res<d[ind1][vec[i]]-a[vec[i]]+d[ind1][tie]-a[tie])
            cnt+=(1<<b[vec[i]]);
    }
    if (cnt*2<=n)
        return max(val, diameter-val);
    else
        return -max(val, diameter-val);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:12:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 |         d[0][i]=getDistance(0, i);
      |                                ^
towns.cpp:22:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |         d[ind1][i]=getDistance(ind1, i);
      |                                ^~~~
towns.cpp:22:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |         d[ind1][i]=getDistance(ind1, i);
      |                                      ^
towns.cpp:58:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   58 |         return -max(val, diameter-val);
      |                ^~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:81:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (long long j=0; j+1<cur.size(); j+=2)
      |                             ~~~^~~~~~~~~~~
towns.cpp:83:55: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   83 |             long long res=getDistance(cur[j], cur[j+1]);
      |                                                       ^
towns.cpp:83:55: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
towns.cpp:101:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |         return max(val, diameter-val);
      |                ~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (long long i=0; i<vec.size(); i++)
      |                         ~^~~~~~~~~~~
towns.cpp:113:46: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |         long long res=getDistance(vec[i], tie);
      |                                              ^
towns.cpp:113:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |         long long res=getDistance(vec[i], tie);
      |                                           ^~~
towns.cpp:118:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  118 |         return max(val, diameter-val);
      |                ~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:120:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |         return -max(val, diameter-val);
      |                ^~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

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