Submission #286448

#	Time	Username	Problem	Language	Result	Execution time	Memory
286448		Puddlestomps	Towns (IOI15_towns)	C++17	0 / 100	22 ms	456 KiB

towns

#include "bits/stdc++.h"

#define TESTING 0

#include "towns.h"
#if TESTING
#include "graderlib.c"
#endif

using namespace std;

typedef long long BEEG;
typedef unsigned long long uBEEG;

int n, root = 0, second = -1;
map<pair<int, int>, int> dists;
map<int, vector<int>> diam;
vector<int> diamdists, offshootpref, diamdiffs, distpref;

pair<int, int> getPair(int a, int b)
{
    int smol = min(a, b);
    int big = a + b - smol;
    return {smol, big};
}

int getEdge(int a, int b)
{
    if(a == b) return 0;
    
    auto edge = getPair(a, b);
    if(dists.count(edge) == 0)
    {
        dists[edge] = getDistance(a, b);
    }

    return dists[edge];
}

int hubDistance(int N, int sub)
{
	n = N;

    int big = 0, bigdist = 0;

    for(int i = 1; i < N; i++)
    {
        int dist = getEdge(root, i);
        if(dist > bigdist)
        {
            bigdist = dist;
            big = i;
        }
    }

    root = big;

    if(TESTING) cerr << "Root: " << root << "\n";

    big = 0;

    for(int i = 0; i < N; i++)
    {
        if(i == root) continue;
        
        int dist = getEdge(root, i);
        if(dist > bigdist)
        {
            bigdist = dist;
            big = i;
        }
    }

    second = big;

    if(TESTING) cerr << "Second: " << second << "\n";

    for(int i = 0; i < N; i++)
    {
        int rootDist = getEdge(root, i), secDist = getEdge(second, i);
        int diff = rootDist - secDist;
        diam[diff].push_back(i);
    }

    int c = 0;
    diamdists.resize(diam.size() - 1, 0);
    diamdiffs.resize(diam.size(), 0);
    diamdiffs[0] = diam.begin()->first;
    int prev = INT_MAX;
    for(auto& it : diam)
    {
        if(prev != INT_MAX)
        {
            diamdists[c++] = (it.first - prev) / 2;
            diamdiffs[c] = it.first;
        }

        prev = it.first;
    }

    if(TESTING)
    {
        cerr << "Diamdists: ";
        for(int i = 0; i < diamdists.size(); i++) cerr << diamdists[i] << " ";
        cerr << "\n";
    }

    offshootpref.resize(diam.size(), 0);
    offshootpref[0] = 1;

    for(int i = 1; i < diam.size(); i++)
    {
        offshootpref[i] = offshootpref[i - 1] + diam[diamdiffs[i]].size();
    }

    if(TESTING)
    {
        cerr << "Nodes Prefix: ";
        for(int i = 0; i < offshootpref.size(); i++) cerr << offshootpref[i] << " ";
        cerr << "\n";
    }

    distpref.resize(diam.size(), 0);
    for(int i = 1; i < diam.size(); i++)
    {
        distpref[i] = distpref[i-1] + diamdists[i - 1];
    }

    if(TESTING)
    {
        cerr << "Dist Prefix: ";
        for(int i = 0; i < distpref.size(); i++) cerr << distpref[i] << " ";
        cerr << "\n";
    }

    int R = INT_MAX;
    vector<int> hubs;

    for(int i = 0; i < diam.size(); i++)
    {
        int rc = distpref[i];
        rc = max(rc, distpref.back() - distpref[i]);
        if(rc < R)
        {
            R = rc;
            hubs.clear();
            hubs.push_back(i);

            if(TESTING) cerr << "New R: " << R << "\n" << "New hub: " << i << "\n";
        }
        else if(rc == R)
        {
            hubs.push_back(i);
            if(TESTING) cerr << "New hub: " << i << "\n";
        }
    }

    //decide if multiply by negative
    
    return R;
}

#if TESTING

int main() {
    FILE *f;
    f = freopen("towns.in","r",stdin);
    assert(f != NULL);
    f = freopen("towns.out","w",stdout);
    assert(f != NULL);
    int ncase, R, N;
    int subtask;
    int ret;
    ret = scanf("%d%d",&subtask,&ncase);
    assert(ret == 2);
    for (int i = 0; i < ncase; i++) {
        ret = scanf("%d",&N);
	assert(ret == 1);
        _ini_query(N,subtask);
        R=hubDistance(N,subtask);
        printf("%d\n",R);
    }
    return 0;
}

#endif

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i = 0; i < diamdists.size(); i++) cerr << diamdists[i] << " ";
      |                        ~~^~~~~~~~~~~~~~~~~~
towns.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i = 1; i < diam.size(); i++)
      |                    ~~^~~~~~~~~~~~~
towns.cpp:113:47: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
  113 |         offshootpref[i] = offshootpref[i - 1] + diam[diamdiffs[i]].size();
towns.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i = 0; i < offshootpref.size(); i++) cerr << offshootpref[i] << " ";
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 1; i < diam.size(); i++)
      |                    ~~^~~~~~~~~~~~~
towns.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int i = 0; i < distpref.size(); i++) cerr << distpref[i] << " ";
      |                        ~~^~~~~~~~~~~~~~~~~
towns.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 0; i < diam.size(); i++)
      |                    ~~^~~~~~~~~~~~~
towns.cpp:40:28: warning: unused parameter 'sub' [-Wunused-parameter]
   40 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

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