Submission #398634

#	Time	Username	Problem	Language	Result	Execution time	Memory
398634		MKopchev	Towns (IOI15_towns)	C++14	100 / 100	29 ms	844 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)
{
    //cout<<"n= "<<n<<endl;

    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;

    map<int,int> seen={};

    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));

            seen[cur]++;
            //cout<<i<<" -> "<<cur<<endl;
        }

    /*
    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=0;
    for(auto w:seen)
    {
        int remain=n-sum-w.second;

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

        if(max(w.first,my_getDistance(u,v)-w.first)==outp)
        {
            if(remain<=n/2&&sum<=n/2&&w.second<=n/2)
            {
                //cout<<"line 107"<<endl;
                return outp;
            }
            if(remain<=n/2&&sum<=n/2)wanted=w.first;
        }
        sum+=w.second;
    }

    if(wanted==-1)
    {
        //cout<<"line 117"<<endl;
        return -outp;
    }
    //cout<<"wanted= "<<wanted<<endl;

    deque< pair<int,int> > remain={};

    for(int i=0;i<n;i++)
        {
            int cur=my_getDistance(0,u)+my_getDistance(u,i)-my_getDistance(0,i);
            cur=cur/2;

            if(cur==wanted)remain.push_back({i,1});
        }

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

    vector< pair<int,int> > to_check={};

    while(remain.size()>2)
    {
        int p=remain.front().first;
        int SZ_p=remain.front().second;
        remain.pop_front();
        if(SZ_p>n/2)return outp;

        int q=remain.front().first;
        int SZ_q=remain.front().second;
        remain.pop_front();
        if(SZ_q>n/2)return outp;

        int score=((my_getDistance(u,p)+my_getDistance(u,q)-my_getDistance(p,q))>2*wanted);

        if(score)
        {
            if(SZ_p+SZ_q>n/2)return outp;
            remain.push_back({p,SZ_p+SZ_q});
        }
        else
        {
            to_check.push_back({p,SZ_p});
            to_check.push_back({q,SZ_q});
        }
    }

    pair<int,int> maj=remain[0];

    for(int i=1;i<remain.size();i++)to_check.push_back(remain[i]);

    for(auto w:to_check)
    {
        int score=((my_getDistance(u,w.first)+my_getDistance(u,maj.first)-my_getDistance(w.first,maj.first))>2*wanted);

        //cout<<"w= "<<w<<" score= "<<score<<endl;

        if(score)maj.second+=w.second;
    }

    //cout<<"score: "<<maj.second<<endl;

    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:68:18: warning: declaration of 'seen' shadows a global declaration [-Wshadow]
   68 |     map<int,int> seen={};
      |                  ^~~~
towns.cpp:35:25: note: shadowed declaration is here
   35 | map< pair<int,int>,int> seen;
      |                         ^~~~
towns.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for(int i=1;i<remain.size();i++)to_check.push_back(remain[i]);
      |                 ~^~~~~~~~~~~~~~
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: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 39 / 39