Submission #432985

#	Time	Username	Problem	Language	Result	Execution time	Memory
432985		wiwiho	Towns (IOI15_towns)	C++14	0 / 100	19 ms	844 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>
 
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
 
using namespace std;
 
typedef long long ll;
 
using pii = pair<int, int>;
 
const ll MOD = 1000000007;

vector<vector<int>> qry;

int n;
int query(int u, int v){
    if(qry[u][v] == -1) qry[u][v] = getDistance(u, v);
    return qry[u][v];
}

vector<int> dis(int v){
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[i] = query(v, i);
    return ans;
}

int hubDistance(int N, int sub){
    n = N;
    qry.resize(n, vector<int>(n, -1));

    vector<int> d0 = dis(0);
    int v1 = max_element(iter(d0)) - d0.begin();
    vector<int> d1 = dis(v1);
    int v2 = max_element(iter(d1)) - d1.begin();
    vector<int> d2 = dis(v2);
    //cerr << v1 << " " << v2 << "\n";

    int dia = query(v1, v2);

    int r = 1000000000;
    for(int i = 0; i < n; i++){
        int sum = query(v1, i) + query(v2, i);
        int oao = (sum - dia) / 2;
        r = min(r, max(query(v1, i), query(v2, i)) - oao);
    }

	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:42:36: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   42 |     int v1 = max_element(iter(d0)) - d0.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:44:36: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   44 |     int v2 = max_element(iter(d1)) - d1.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:37:28: warning: unused parameter 'sub' [-Wunused-parameter]
   37 | 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