oj.uz

Submission #398594

# Submission time Handle Problem Language Result Execution time Memory
398594 2021-05-04T15:15:05 Z MKopchev Towns (IOI15_towns) C++14
13 / 100
 27 ms 496 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 332 KB Output is correct
2 Correct 24 ms 324 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 27 ms 496 KB Output is correct
5 Correct 26 ms 332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 388 KB Output is correct
2 Correct 18 ms 332 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 340 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -