Submission #1096814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096814		MMihalev	Towns (IOI15_towns)	C++17	10 / 100	9 ms	604 KiB

towns

#include "towns.h"
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
bool checked[MAX_N][MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
set<int>nodes,nodes1,nodes2;
int n;
int u,v;
int q;

int parent[MAX_N];
int s[MAX_N];

int Find(int a)
{
    if(parent[a]==a)return a;
    return parent[a]=Find(parent[a]);
}

void Merge(int a,int b)
{
    int urt=Find(a);
    int vrt=Find(b);
    if(urt==vrt)return;

    if(s[urt]>s[vrt])swap(urt,vrt);

    parent[urt]=vrt;
    s[vrt]+=s[urt];
}

bool check(int a,int b)
{
    int dd;
    if(a>b)swap(a,b);
    checked[a][b]=1;
    if(ma[a][b])dd=ma[a][b];
    else
    {
        if(q>(9*n+1)/2)while(1);
        dd=getDistance(a,b);
        ma[a][b]=dd;
        q++;
    }

    if(tou[a]+tov[b]-diam==dd)return 0;
    Merge(a,b);
    return 1;
}
int hubDistance(int N, int sub)
{
    q=0;
    nodes1.clear();
    nodes2.clear();
    n=N;
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        s[i]=1;

        to0[i]=0;
        tou[i]=0;
        tov[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            checked[i][j]=0;
            ma[i][j]=0;
        }
    }

    u=0;
    int far=0;
    for(int i=1;i<n;i++)
    {
        int cur=getDistance(u,i);
        ma[0][i]=cur;
        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
        {
            q++;
            cur=getDistance(i,v);
            ma[min(i,v)][max(i,v)]=cur;
        }

        tov[i]=cur;

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

    for(int i=0;i<n;i++)
    {
        tou[i]=to0[i];
    }//u->all


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

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

        int x=tov[i];
        int y=to0[i];

        x=(x-y+tov[0])/2;

        int res=min(abs((diam+1)/2-x),abs(diam/2-x));

        if(res<mindif)
        {
            mindif=res;
            dis1=x;
            dis2=0;
        }
        else if(res==mindif && x!=dis1)
        {
            dis2=x;
        }
    }

    if(dis1>dis2)swap(dis1,dis2);

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

        int x=tov[i];
        int y=to0[i];

        x=(x-y+tov[0])/2;

        if(x==dis1 or x==dis2)
        {
            if(x==dis2){cntbaseneg++;nodes1.insert(i);}
            else {cntbasepos++;nodes2.insert(i);}
        }
        else if(x>dis2)cntneg++;
        else cntpos++;
    }

    int R=0;
    R=max(R,dis2);
    R=max(R,diam-dis2);
    if(dis1!=0)
    {
        R=max(R,dis1);
        R=max(R,diam-dis1);
    }

    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;

    set<int>NO=nodes;

    int overhalf=-1;
    int other=-1;

    while(nodes.size())
    {
        if(nodes.size()==2)
        {
            overhalf=(*(nodes.begin()));
            nodes.erase(overhalf);
            other=(*(nodes.begin()));

            if(check(overhalf,other))
            {
                other=-1;
            }
            break;
        }
        if(nodes.size()==1){overhalf=(*(nodes.begin()));break;}
        vector<int>nod;
        set<int>nnodes;
        for(int x:nodes)nod.push_back(x);
        for(int i=1;i<nod.size();i+=2)
        {
            if(check(nod[i],nod[i-1]))nnodes.insert(nod[i]);
        }
        if((nod.size())%2==1)
        {
            int sz=nod.size();
            nnodes.insert(nod[sz-1]);
        }
        nodes=nnodes;
    }

    if(overhalf==-1)return R;

    int cnt=0;
    for(int i:NO)
    {
        if(Find(i)==Find(overhalf)){cnt++;continue;}

        bool no=0;

        for(int r:NO)
        {
            if(Find(r)==Find(overhalf))
            {
                for(int p:NO)
                {
                    if(Find(p)==Find(i))
                    {
                        if(checked[min(p,r)][max(p,r)])no=1;
                    }
                    if(no)break;
                }
            }
            if(no)break;
        }

        if(no)continue;

        if(check(i,overhalf))cnt++;
    }

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

    cnt=0;
    overhalf=other;

    if(overhalf==-1)return R;

    for(int i:NO)
    {
        if(Find(i)==Find(overhalf)){cnt++;continue;}

        bool no=0;

        for(int r:NO)
        {
            if(Find(r)==Find(overhalf))
            {
                for(int p:NO)
                {
                    if(Find(p)==Find(i))
                    {
                        if(checked[min(p,r)][max(p,r)])no=1;
                    }
                    if(no)break;
                }
            }
            if(no)break;
        }

        if(no)continue;

        if(check(i,overhalf))cnt++;
    }

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

	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:228:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |         for(int i=1;i<nod.size();i+=2)
      |                     ~^~~~~~~~~~~
towns.cpp:234:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  234 |             int sz=nod.size();
      |                    ~~~~~~~~^~

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