Submission #1065890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065890		anango	Towns (IOI15_towns)	C++17	0 / 100	9 ms	856 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int INF = 1LL<<60;
int n;

map<pair<int,int>,int> cache;

int getdist(int u, int v) {
    if (u==v) {
        return 0;
    }
    if (u>v) swap(u,v);
    if (cache.count({u,v})) {
        return cache[{u,v}];
    }
    return cache[{u,v}] = getDistance(u,v);
}

signed hubDistance(signed N, signed sub) {
    n=N;
    
    vector<int> dist0(n);
    for (int i=0; i<n; i++) {
        dist0[i] = getdist(0,i);
    }
    vector<int> cities(n); iota(cities.begin(), cities.end(), (int)0);
    vector<int> sortedbyd0(cities.begin(), cities.end());
    sort(sortedbyd0.begin(), sortedbyd0.end(), [&](const int i1, const int i2) {
        return dist0[i1]<dist0[i2];
    });
    int u = sortedbyd0.back();
    vector<int> distu(n);
    for (int i=0; i<n; i++) {
        distu[i] = getdist(u,i);
    }
    
    //2n-3 used
    vector<int> sortedbydu(cities.begin(), cities.end());
    sort(sortedbydu.begin(), sortedbydu.end(), [&](const int i1, const int i2) {
        return distu[i1]<distu[i2];
    });
    int v = sortedbydu.back();
    //u-v is a diameter
    int length = distu[v];
    int mindiff = INF;
    for (int i=0; i<n; i++) {
        mindiff = min(mindiff,abs(getdist(i,u)-getdist(i,v)));
    }
    assert(length%2==mindiff%2);
	return (length+mindiff)/2;
}

Compilation message (stderr)

towns.cpp: In function 'long long int getdist(long long int, long long int)':
towns.cpp:19:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     return cache[{u,v}] = getDistance(u,v);
      |                                       ^
towns.cpp:19:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     return cache[{u,v}] = getDistance(u,v);
      |                                         ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:53:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   53 |  return (length+mindiff)/2;
      |         ~~~~~~~~~~~~~~~~^~
towns.cpp:22:37: warning: unused parameter 'sub' [-Wunused-parameter]
   22 | signed hubDistance(signed N, signed 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