Submission #398557

#	Time	Username	Problem	Language	Result	Execution time	Memory
398557		MKopchev	Towns (IOI15_towns)	C++14	25 / 100	27 ms	1136 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
/*
static int _N;
static int _dist[110][110];
static int _quota, _user_query;

void _ini_query(int N, int k) {
    int ret;
    _N = N;
    for (int i = 0; i < _N; i++)
        for (int j = 0; j < _N; j++)  {
	    ret = scanf("%d", &_dist[i][j]);
            assert(ret == 1);
        }
    if (k == 1 || k == 3) _quota = _N * (_N - 1) / 2;
    else if (k == 2 || k == 4 || k == 6) _quota = (7 * _N + 1) / 2;
    else _quota = 5 * _N;
    _user_query = 0;
}


int getDistance(int i, int j) {
    _user_query++;
    if (_user_query > _quota) {
        printf("0\n");
        exit(0);
    }
    if (i < 0 || i >= _N) return 0;
    if (j < 0 || j >= _N) return 0;
    return _dist[i][j];
}
*/
map< pair<int,int>,int> seen;

int my_getDistance(int i,int j)
{
    if(i==j)return 0;

    if(seen.count({i,j}))return seen[{i,j}];
    int d=getDistance(i,j);

    seen[{i,j}]=d;
    seen[{j,i}]=d;
    return d;
}
int hubDistance(int n, int subtask)
{
    seen={};

    int u=1;
    for(int i=2;i<n;i++)
    {
        if(my_getDistance(0,u)<my_getDistance(0,i))u=i;
    }

    int v=0;
    for(int i=1;i<n;i++)
    {
        if(my_getDistance(u,v)<my_getDistance(u,i))v=i;
    }

    //cout<<"diameter "<<u<<" "<<v<<endl;

    int outp=1e9;
    for(int i=0;i<n;i++)
        if(i!=u&&i!=v)
        {
            int cur=my_getDistance(u,v)+my_getDistance(i,u)-my_getDistance(i,v);
            cur=cur/2;

            outp=min(outp,max(cur,my_getDistance(v,u)-cur));
        }

    return outp;
}
/*
int main()
{
    int ncase, R, N;
    int subtask;
    int ret;
    ret = scanf("%d%d",&subtask,&ncase);
    assert(ret == 2);
    for (int i = 0; i < ncase; i++) {
        ret = scanf("%d",&N);
        assert(ret == 1);
        _ini_query(N,subtask);
        R=hubDistance(N,subtask);
        printf("%d %d\n",R,_user_query);
    }
}
*/

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   48 | int hubDistance(int n, int subtask)
      |                        ~~~~^~~~~~~

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