Submission #398594

#	Time	Username	Problem	Language	Result	Execution time	Memory
398594		MKopchev	Towns (IOI15_towns)	C++14	13 / 100	27 ms	496 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(0,u)+my_getDistance(u,i)-my_getDistance(0,i);
            cur=cur/2;

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

            //cout<<i<<" -> "<<cur<<endl;
        }

    map<int,int> seen={};

    for(int i=1;i<n;i++)
        if(i!=u)
        {
            int d=my_getDistance(0,i)+my_getDistance(0,u)-my_getDistance(i,u);
            d=d/2;

            seen[d]++;

            //cout<<i<<" -> "<<d<<endl;
        }

    int wanted=-1;

    int sum=1;
    for(auto w:seen)
    {
        int remain=n-sum-w.second;

        //cout<<w.second<<" "<<sum<<" "<<remain<<endl;

        if(remain<=n/2&&sum<=n/2&&w.second<=n/2)return outp;
        if(remain<=n/2&&sum<=n/2)wanted=w.first;

        sum+=w.second;
    }

    if(wanted==-1)return -outp;

    vector<int> remain={};

    for(int i=1;i<n;i++)
        if(i!=u)
        {
            int d=my_getDistance(0,i)+my_getDistance(0,u)-my_getDistance(i,u);
            d=d/2;

            if(d==wanted)remain.push_back(i);
        }

    //for(auto w:remain)cout<<w<<" ";cout<<endl;

    pair<int,int> maj={0,0};
    for(auto w:remain)
    {
        if(maj.second==0)maj={w,1};
        else
        {
            if(my_getDistance(w,maj.first)==my_getDistance(0,w)-wanted+my_getDistance(0,maj.first)-wanted)maj.second--;
            else maj.second++;
        }
    }

    maj.second=0;
    for(auto w:remain)
    {
        if(my_getDistance(w,maj.first)!=my_getDistance(0,w)-wanted+my_getDistance(0,maj.first)-wanted)maj.second++;
    }

    if(maj.second>n/2)return -outp;
    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:78:18: warning: declaration of 'seen' shadows a global declaration [-Wshadow]
   78 |     map<int,int> seen={};
      |                  ^~~~
towns.cpp:35:25: note: shadowed declaration is here
   35 | map< pair<int,int>,int> seen;
      |                         ^~~~
towns.cpp:48:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   48 | int hubDistance(int n, int subtask)
      |                        ~~~~^~~~~~~

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