Submission #787836

#	Time	Username	Problem	Language	Result	Execution time	Memory
787836		vnm06	Towns (IOI15_towns)	C++14	13 / 100	18 ms	460 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;

int st[150][150];

int pitaj(int i, int j)
{
    if(st[i][j]!=-1) return st[i][j];
    st[i][j]=getDistance(i, j);
    st[j][i]=st[i][j];
    return st[i][j];
}

int par[150], db[150];
int brk[150];
vector<int> vr1, vr2;

int hubDistance(int N, int sub)
{
    for(int i=0; i<150; i++) {par[i]=i; db[i]=1; brk[i]=1;}
    vr1.resize(0);
    vr2.resize(0);
    int n=N;
    memset(st, -1, sizeof(st));
    for(int i=0; i<n; i++) st[i][i]=0;
    int v1=0;
    for(int i=1; i<n; i++)
    {
        if(pitaj(0, i)>pitaj(0, v1)) v1=i;
    }
    int v2=0;
    for(int i=0; i<n; i++)
    {
        if(pitaj(v1, i)>pitaj(v1, v2)) v2=i;
    }
    int R=1e9, bro=0;
    int d1;
    int d2;
    for(int i=0; i<n; i++)
    {
        if(i==v1 || i==v2) continue;
        int t1=pitaj(i, v1);
        int t2=pitaj(i, v2);
        int t3=pitaj(v1, v2);
        int r1=(t1+t3-t2)/2, r2=(t2+t3-t1)/2;
        if(max(r1, r2)<R)
        {
            R=max(r1, r2);
            bro=1;
            d1=r1;
        }
        else if(max(r1, r2)==R)
        {
            bro=2;
            d2=r1;
        }
    }
    if(bro>1 && d1>d2) swap(d1, d2);
    int br1=0, br2=0;
    for(int i=0; i<n; i++)
    {
        int t1=pitaj(i, v1);
        int t2=pitaj(i, v2);
        int t3=pitaj(v1, v2);
        int r1=(t1+t3-t2)/2;
        if(r1==d1) vr1.push_back(i);
        if(bro>1 && r1==d2) vr2.push_back(i);
        if(r1<=d1) br1++;
        else br2++;
    }
    if(br1<=N/2 && br2<=N/2) return R;
    if(br1<=N/2)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                int t1=pitaj(i, v1);
                int t2=pitaj(i, v2);
                int t3=pitaj(v1, v2);
                int tr11=(t1+t3-t2)/2;
                int s1=pitaj(j, v1);
                int s2=pitaj(j, v2);
                int s3=pitaj(v1, v2);
                int ts11=(s1+s3-s2)/2;
                int bt=pitaj(i, j);
                if(((tr11<d2 && ts11<d2) || (tr11<d2 && ts11<d2))
                   || (tr11==d2 && ts11==d2 && (t1+t2-t3)/2+(s1+s2-s3)/2!=bt))
                {
                    int i2=i, j2=j;
                    while(i2!=par[i2]) i2=par[i2];
                    while(j2!=par[j2]) j2=par[j2];
                    if(i2==j2) continue;
                    if(db[i2]>db[j2])
                    {
                        par[j2]=i2;
                        brk[i2]+=brk[j2];
                        if(brk[i2]>n/2) return -R;
                    }
                    else if(db[i2]<db[j2])
                    {
                        par[i2]=j2;
                        brk[j2]+=brk[i2];
                        if(brk[j2]>n/2) return -R;

                    }
                    else
                    {
                        par[j2]=i2;
                        db[i2]++;
                        brk[i2]+=brk[j2];
                        if(brk[i2]>n/2) return -R;

                    }

                }
            }
        }
        return R;
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                int t1=pitaj(i, v1);
                int t2=pitaj(i, v2);
                int t3=pitaj(v1, v2);
                int tr11=(t1+t3-t2)/2;
                int s1=pitaj(j, v1);
                int s2=pitaj(j, v2);
                int s3=pitaj(v1, v2);
                int ts11=(s1+s3-s2)/2;
                int bt=pitaj(i, j);
                if(((tr11<d1 && ts11<d1) || (tr11<d1 && ts11<d1))
                   || (tr11==d1 && ts11==d1 && (t1+t2-t3)/2+(s1+s2-s3)/2!=bt))
                {
                    int i2=i, j2=j;
                    while(i2!=par[i2]) i2=par[i2];
                    while(j2!=par[j2]) j2=par[j2];
                    if(i2==j2) continue;
                    if(db[i2]>db[j2])
                    {
                        par[j2]=i2;
                        brk[i2]+=brk[j2];
                        if(brk[i2]>n/2) return -R;
                    }
                    else if(db[i2]<db[j2])
                    {
                        par[i2]=j2;
                        brk[j2]+=brk[i2];
                        if(brk[j2]>n/2) return -R;

                    }
                    else
                    {
                        par[j2]=i2;
                        db[i2]++;
                        brk[i2]+=brk[j2];
                        if(brk[i2]>n/2) return -R;

                    }

                }
            }
        }
        return R;

    }
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:19:28: warning: unused parameter 'sub' [-Wunused-parameter]
   19 | int hubDistance(int N, int sub)
      |                        ~~~~^~~
towns.cpp:59:14: warning: 'd2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     if(bro>1 && d1>d2) swap(d1, d2);
      |        ~~~~~~^~~~~~~~
towns.cpp:59:14: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]

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