Submission #1065897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065897		anango	Towns (IOI15_towns)	C++17	25 / 100	17 ms	868 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}];
    }
    int g = getDistance(u,v);
    //cout << "DISTANCE " << u <<" " << v <<" " << g << endl;
    return cache[{u,v}] = g;
}

signed hubDistance(signed N, signed sub) {
    cache.clear();
    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)));
            //cout << i <<" " << getdist(i,u) <<" " << getdist(i,v) << endl;
        }
        //cout << u <<" " << v <<" " << length <<" " << mindiff <<" " << (length+mindiff)/2 << endl;

        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:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     int g = getDistance(u,v);
      |                         ^
towns.cpp:19:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |     int g = getDistance(u,v);
      |                           ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:60:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |         return (length+mindiff)/2;
      |                ~~~~~~~~~~~~~~~~^~

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