Submission #433994

#	Time	Username	Problem	Language	Result	Execution time	Memory
433994		79brue	Towns (IOI15_towns)	C++14	0 / 100	16 ms	460 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

typedef long long ll;

int n, k;
int x, y, len;
int a[120], b[120];

vector<int> dist;
map<int, int> idx;

int branch[120], loc[120];
vector<pair<int, int> > vec[120];
int maxB[120];

int R=1e9, C; bool twoC;
bool centroidExist;

int hubDistance(int N, int sub){
	n = N;
	x = 0;
	for(int i=0; i<n; i++){
        if(i!=x) a[i] = getDistance(x, i);
	}
	y = max_element(a, a+n) - a;
	len = a[y];
	for(int i=0; i<n; i++){
        if(i==x) b[i] = len;
        else if(i!=y) b[i] = getDistance(y, i);
	}

    dist.push_back(0);
    dist.push_back(len);
	for(int i=0; i<n; i++){
        if(i==x || i==y) continue;
        branch[i] = (a[i] + b[i] - len) / 2;
        dist.push_back(a[i] - branch[i]);
	}

	sort(dist.begin(), dist.end());
	dist.erase(unique(dist.begin(), dist.end()), dist.end());
	for(int i=0; i<(int)dist.size(); i++){
        idx[dist[i]] = i;
	}

    int k = (int)dist.size();
    for(int i=0; i<n; i++){
        if(i==x || i==y) continue;
        loc[i] = idx[a[i] - branch[i]];
        vec[loc[i]].push_back(make_pair(i, branch[i]));
        maxB[loc[i]] = max(maxB[loc[i]], branch[i]);
    }

    for(int i=0; i<k; i++){
        int maxLen = -1;
        for(int j=0; j<k; j++){
            maxLen = max(maxLen, abs(dist[i] - dist[j]) + maxB[j]);
        }
        if(maxLen < R){
            R = maxLen;
            C = i;
        }
        else if(maxLen == R) twoC = 1;
    }

    return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:28:26: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   28 |  y = max_element(a, a+n) - a;
      |      ~~~~~~~~~~~~~~~~~~~~^~~
towns.cpp:49:9: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   49 |     int k = (int)dist.size();
      |         ^
towns.cpp:8:8: note: shadowed declaration is here
    8 | int n, k;
      |        ^
towns.cpp:22:28: warning: unused parameter 'sub' [-Wunused-parameter]
   22 | 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