oj.uz

Submission #1063834

# Submission time Handle Problem Language Result Execution time Memory
1063834 2024-08-18T04:04:25 Z Hanksburger Towns (IOI15_towns) C++17
100 / 100
 14 ms 1116 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1112 KB Output is correct
2 Correct 10 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 860 KB Output is correct
5 Correct 10 ms 860 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct
2 Correct 8 ms 844 KB Output is correct
3 Correct 11 ms 1000 KB Output is correct
4 Correct 14 ms 868 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 10 ms 988 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 10 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1116 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 10 ms 864 KB Output is correct
3 Correct 10 ms 864 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 10 ms 864 KB Output is correct
3 Correct 10 ms 860 KB Output is correct