Submission #1096750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096750		MMihalev	Towns (IOI15_towns)	C++17	35 / 100	1081 ms	600 KiB

towns

#include "towns.h"
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
int q;
set<int>nodes,nodes1,nodes2;
int n;
int u,v;
bool check(int a,int b)
{
    int dd;
    if(a>b)swap(a,b);
    if(a==0)dd=to0[b];
    else
    {
        //if(q==(n*(n-1))/2)while(1);
        if(ma[a][b])
        {
            if(a==u or a==v)while(1);
            if(b==u or b==v)while(1);
        }
        ma[a][b]=1;
        dd=getDistance(a,b);
        q++;
    }

    if(tou[a]+tov[b]-diam==dd)return 0;
    return 1;
}
int hubDistance(int N, int sub)
{
    n=N;

    u=0;
    int far=0;
    for(int i=1;i<n;i++)
    {
        int cur=getDistance(u,i);
        q++;
        to0[i]=cur;
        if(cur>far)
        {
            far=cur;
            v=i;
        }
    }//0->v

    diam=0;
    for(int i=0;i<n;i++)
    {
        if(i==v)continue;
        int cur;
        if(i==0)cur=to0[v];
        else {cur=getDistance(i,v);q++;}

        tov[i]=cur;

        if(cur>diam)
        {
            diam=cur;
            u=i;
        }
    }//v->u

    for(int i=0;i<n;i++)
    {
        if(i==u)continue;
        if(i==0){tou[i]=to0[u];continue;}
        if(i==v){tou[i]=tov[u];continue;}

        if(u!=0){tou[i]=getDistance(u,i);q++;}
        else tou[i]=to0[i];
    }//u->all


    int cntneg=1,cntpos=1,cntbaseneg=0,cntbasepos=0;
    int mindif=1e9;

    for(int i=0;i<n;i++)
    {
        if(i==u or i==v)continue;

        int x=tou[i];
        int y=tov[i];
        int com=((x+y)-diam)/2;

        x-=com;
        y-=com;

        int res=x-y;

        mindif=min(mindif,abs(res));
    }

    for(int i=0;i<n;i++)
    {
        if(i==u or i==v)continue;

        int x=tou[i];
        int y=tov[i];
        int com=((x+y)-diam)/2;

        x-=com;
        y-=com;

        int res=x-y;

        if(abs(res)==mindif)
        {
            if(res<=0){cntbaseneg++;nodes1.insert(i);}
            else {cntbasepos++;nodes2.insert(i);}
        }
        else if(res<0)cntneg++;
        else cntpos++;
    }

    int R=(diam-mindif)/2+mindif;

    if(sub==4 or sub<=2)
    {
        if(cntbaseneg*cntbasepos!=0)
        {
            if(cntneg*2>n or (cntbasepos+cntpos)*2>n or cntbaseneg*2>n)return -R;
            if(cntpos*2>n or (cntbaseneg+cntneg)*2>n or cntbasepos*2>n)return -R;
            return R;
        }
        else
        {
            if(cntneg*2>n or cntpos*2>n or (cntbaseneg+cntbasepos)*2>n)return -R;
            return R;
        }
    }

    if(cntneg*2>n or cntpos*2>n)return -R;

    if(cntbasepos*2<=n && cntbaseneg*2<=n)return R;

    if(cntbaseneg*2>n)nodes=nodes1;
    else nodes=nodes2;

    while(nodes.size())
    {
        int cnt=1;
        int uu=(*(nodes.begin()));
        nodes.erase(uu);
        if(nodes.size()==0)break;

        auto it=nodes.begin();
        set<int>dele;
        while(it!=nodes.end())
        {
            if(check(uu,(*it)))
            {
                dele.insert((*it));
                cnt++;
            }
            it++;
        }

        while(dele.size())
        {
            int el=(*(dele.begin()));
            dele.erase(el);
            nodes.erase(el);
        }

        if(2*cnt>n)return -R;
    }

	return R;
}

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