Submission #1065891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065891		anango	Towns (IOI15_towns)	C++17	0 / 100	12 ms	600 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) {
    if (sub<=2) {
        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;
    }
    else {
        return 0;
    }

}

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:54:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |         return (length+mindiff)/2;
      |                ~~~~~~~~~~~~~~~~^~

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