Submission #1071235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071235		ibm2006	Towns (IOI15_towns)	C++17	100 / 100	55 ms	31876 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
vector<ll> v[1100000],u,b,another,good;
ll get_Distance(ll x,ll y)
{
    x--;
    y--;
    return getDistance(x,y);
}
void set_dist(ll x,ll y,ll z)
{
    adj[x][y]=z;
    adj[y][x]=z;
}
ll get_dist(ll x,ll y)
{
    return adj[x][y];
}
ll check_balanced(vector<ll> a,bool asd)
{
    //printf("!");
    ll i;
    for(i=0;i<=n;i++)
    {
        num[i]=0;
        fir[i]=0;
        c[i]=0;
        up[i]=0;
    }
    if(!asd)
    {b.clear();
    for(i=0;i<a.size();i++)
    {
        b.push_back((get_dist(a[i],1)+get_dist(a[i],x)-get_dist(x,1))/2);
    }}
    else
    {
        b.clear();
        for(i=0;i<a.size();i++)
        {
            b.push_back((get_dist(a[i],1)-len));
        }
    }
    ll s=0,t=0,gr=0;
    for(i=0;i<a.size();i++)
    {
        if(t==0)
        {
            gr++;
            num[gr]++;
            fir[gr]=i;
            s=i;
            c[i]=s;
            t++;
            up[i]=1;
            continue;
        }
        else
        {
            num[gr]++;
            c[i]=c[i-1];
            up[i]=1;
            if(b[i]+b[s]==get_Distance(a[i],a[s]))
            {
                up[i]=0;
                t--;
            }
            else
                t++;
        }
    }
    t=0;
    for(i=1;i<gr;i++)
    {
        if(b[fir[i]]+b[s]!=get_Distance(a[fir[i]],a[s]))
        {
            t+=num[i]/2;
            continue;
        }
        for(j=fir[i];j<fir[i+1];j++)
        {
            if(up[j])
                continue;
            if(b[j]+b[s]!=get_Distance(a[j],a[s]))
            {
                t++;
            }
        }
    }
    for(j=fir[gr];j<a.size();j++)
    {
        if(up[j])
            t++;
    }
    if(t<=mid)
        return 1;
    else
        return 0;
}
int hubDistance(int N, int sub) {
	n=N;
	for(i=0;i<=1000000;i++)
    {
        v[i].clear();
    }
    u.clear();
    another.clear();
    ans=0;
    good.clear();
	mid=n/2;
	x=1;
	z=0;
	y=0;
	for(i=1;i<=n;i++)
    {
        if(i==x)
            continue;
        w=get_Distance(x,i);
        set_dist(x,i,w);
        if(w>z)
        {
            z=w;
            y=i;
        }
    }
    x=0;
    z=0;
    for(i=1;i<=n;i++)
    {
        if(i==y)
            continue;
        w=get_Distance(y,i);
        set_dist(y,i,w);
        if(w>z)
        {
            z=w;
            x=i;
        }
    }
    swap(x,y);
    //printf("(%lld,%lld)\n",x,y);
    len=(get_dist(1,y)+get_dist(1,x)-get_dist(x,y))/2;
    asdf=get_dist(1,x)-len;
    //printf("(%lld,%lld)\n",len,asdf);
    for(i=1;i<=n;i++)
    {
        z=get_dist(1,i)-get_dist(x,i);
        if(z==len-asdf&&get_dist(1,i)!=0)
        {
            another.push_back(i);
            continue;
        }
        if(z<=len-asdf)
        {
            good.push_back(i);
            continue;
        }
        k=asdf-(z-len+asdf)/2;
        u.push_back(k);
        v[k].push_back(i);
    }
    u.push_back(asdf);
    sort(u.begin(),u.end());
    reverse(u.begin(),u.end());
    u.erase(unique(u.begin(),u.end()),u.end());
    s=10000000;
    for(i=0;i<u.size();i++)
    {
        //printf("(%lld)",u[i]);
        s=min(s,max(get_dist(x,y)-u[i],u[i]));
    }
    //printf("\n");
    siz=0;
    for(i=0;i<u.size();i++)
    {
        if(max(get_dist(x,y)-u[i],u[i])==s)
        {
            if(u[i]==len)
                continue;
            z=good.size()+another.size()+siz;
            w=n-z-v[u[i]].size();
            if(z>mid||w>mid)
            {

            }
            else
            {
                if(v[u[i]].size()<=mid)
                {
                    ans=1;
                }
                else
            ans|=check_balanced(v[u[i]],false);
            }
        }
        if(u[i]!=len)
            siz+=v[u[i]].size();
    }
    if(max(get_dist(x,y)-asdf,asdf)==s)
    {
        z=n-another.size()-good.size();
        //printf("[%lld %lld]\n",z,good.size());
        if(z<=mid&&good.size()<=mid)
        {
            if(another.size()<=mid)
                ans=1;
            else
            ans|=check_balanced(another,true);}
    }
    if(ans)
    ans=1;
    else
    ans=-1;
    return s*ans;
}

Compilation message (stderr)

towns.cpp: In function 'll get_Distance(ll, ll)':
towns.cpp:7:25: warning: declaration of 'y' shadows a global declaration [-Wshadow]
    7 | ll get_Distance(ll x,ll y)
      |                      ~~~^
towns.cpp:5:20: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                    ^
towns.cpp:7:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
    7 | ll get_Distance(ll x,ll y)
      |                 ~~~^
towns.cpp:5:18: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                  ^
towns.cpp: In function 'void set_dist(ll, ll, ll)':
towns.cpp:13:28: warning: declaration of 'z' shadows a global declaration [-Wshadow]
   13 | void set_dist(ll x,ll y,ll z)
      |                         ~~~^
towns.cpp:5:22: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                      ^
towns.cpp:13:23: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   13 | void set_dist(ll x,ll y,ll z)
      |                    ~~~^
towns.cpp:5:20: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                    ^
towns.cpp:13:18: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   13 | void set_dist(ll x,ll y,ll z)
      |               ~~~^
towns.cpp:5:18: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                  ^
towns.cpp: In function 'll get_dist(ll, ll)':
towns.cpp:18:21: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   18 | ll get_dist(ll x,ll y)
      |                  ~~~^
towns.cpp:5:20: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                    ^
towns.cpp:18:16: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   18 | ll get_dist(ll x,ll y)
      |             ~~~^
towns.cpp:5:18: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                  ^
towns.cpp: In function 'll check_balanced(std::vector<int>, bool)':
towns.cpp:22:30: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   22 | ll check_balanced(vector<ll> a,bool asd)
      |                   ~~~~~~~~~~~^
towns.cpp:5:30: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                              ^
towns.cpp:25:8: warning: declaration of 'i' shadows a global declaration [-Wshadow]
   25 |     ll i;
      |        ^
towns.cpp:5:8: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |        ^
towns.cpp:35:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(i=0;i<a.size();i++)
      |             ~^~~~~~~~~
towns.cpp:42:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(i=0;i<a.size();i++)
      |                 ~^~~~~~~~~
towns.cpp:47:8: warning: declaration of 's' shadows a global declaration [-Wshadow]
   47 |     ll s=0,t=0,gr=0;
      |        ^
towns.cpp:5:26: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                          ^
towns.cpp:47:12: warning: declaration of 't' shadows a global declaration [-Wshadow]
   47 |     ll s=0,t=0,gr=0;
      |            ^
towns.cpp:5:28: note: shadowed declaration is here
    5 | ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],c[1100000],num[110000],up[110000],fir[110000],adj[1100][1100],mid,len,asdf,siz,ans;
      |                            ^
towns.cpp:48:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(i=0;i<a.size();i++)
      |             ~^~~~~~~~~
towns.cpp:93:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(j=fir[gr];j<a.size();j++)
      |                   ~^~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:170:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
towns.cpp:177:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(i=0;i<u.size();i++)
      |             ~^~~~~~~~~
towns.cpp:183:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  183 |             z=good.size()+another.size()+siz;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:184:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  184 |             w=n-z-v[u[i]].size();
      |               ~~~^~~~~~~~~~~~~~~
towns.cpp:191:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  191 |                 if(v[u[i]].size()<=mid)
      |                    ~~~~~~~~~~~~~~^~~~~
towns.cpp:200:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  200 |             siz+=v[u[i]].size();
      |                               ^
towns.cpp:204:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} may change value [-Wconversion]
  204 |         z=n-another.size()-good.size();
      |           ~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:206:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  206 |         if(z<=mid&&good.size()<=mid)
      |                    ~~~~~~~~~~~^~~~~
towns.cpp:208:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  208 |             if(another.size()<=mid)
      |                ~~~~~~~~~~~~~~^~~~~
towns.cpp:103:28: warning: unused parameter 'sub' [-Wunused-parameter]
  103 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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