Submission #1313639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313639		activedeltorre	Towns (IOI15_towns)	C++20	61 / 100	9 ms	456 KiB

towns

#include "towns.h"
using namespace std;
#include <map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
int rez[225][5];
int distdiam[225];
int getmax(int n,int b,int id)
{
    int best=-1,can=0;
    for(int i=0; i<n; i++)
    {
        rez[i][id]=getDistance(b,i);
        if(rez[i][id]>best)
        {
            best=rez[i][id];
            can=i;
        }
    }
    return can;
}
map<int,int>mp;
map<int,vector<int>>noduri;
int majoritar(vector<int>vec,int nmax)
{
    int can=vec[0],off=1;
    for(int i=1; i<vec.size(); i++)
    {
        if(getDistance(can,vec[i])==distdiam[can]+distdiam[vec[i]])
        {
            off--;
            if(off<0)
            {
                can=vec[i];
                off=1;
            }
        }
        else
        {
            off++;
        }
    }
    off=0;
    for(int i=0; i<vec.size(); i++)
    {
        if(getDistance(can,vec[i])!=distdiam[can]+distdiam[vec[i]]){
            off++;
        }
    }
    if(off>nmax)
    {
        return 1;
    }
    return 0;
}
int hubDistance(int N, int sub)
{
    mp.clear();
    noduri.clear();
    int d1=getmax(N,1,0);
    int d2=getmax(N,d1,1);
    int d3=getmax(N,d2,2);
    int dab=rez[d2][1];
    int minim=1000000000;
    for(int i=0; i<N; i++)
    {
        if(i!=d1 && i!=d2)
        {
            int distodim=(rez[i][1]+rez[i][2]-dab)/2;
            distdiam[i]=distodim;
            int x=(rez[i][1]-distodim);
            int y=(rez[i][2]-distodim);
            int diff=x-y;
            mp[diff]++;
            noduri[diff].push_back(i);
            minim=min(minim,abs(diff));
        }
    }
    int prefix=1;
    int semn=-1;
    int r=(dab+minim)/2;
    int nmax=N/2;
    for(auto it:mp)
    {
        if(abs(it.first)==(minim))
        {
            if(it.second<=nmax && prefix<=nmax && N-prefix-it.second<=nmax)
            {
                semn=1;
            }
            else if(sub!=2 && sub!=4 && prefix<=nmax && N-prefix-it.second<=nmax)
            {
                if(majoritar(noduri[it.first],nmax)==0)
                {
                    semn=1;
                }
            }
        }
        prefix=prefix+it.second;
        noduri[it.first].clear();
    }
    noduri.clear();
    return r*semn;
}

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