Submission #705971

#	Time	Username	Problem	Language	Result	Execution time	Memory
705971		bin9638	Towns (IOI15_towns)	C++17	35 / 100	14 ms	436 KiB

towns

#include <bits/stdc++.h>
 
#ifndef SKY
#include<towns.h>
#endif
 
using namespace std;
 
#define ll long long
#define fs first
#define sc second
#define N 210
#define pb push_back
#define ii pair<ll,ll>
 
int dis[N][N],c[N][N];
vector<int>hub;
 
#ifdef SKY
int getDistance(int i, int j)
{
    return dis[i][j];
}
#endif // SKY
 
 
int hubDistance(int n, int sub)
{
    for(int i=1;i<n;i++)
        c[0][i]=c[i][0]=getDistance(0,i);
    int S=1;
    for(int i=1;i<n;i++)
        if(c[0][i]>c[0][S])
            S=i;
    // da tinh 0
    for(int i=1;i<n;i++)
        if(i!=S)
            c[S][i]=c[i][S]=getDistance(S,i);
    int T=0;
    for(int i=0;i<n;i++)
        if(c[S][i]>c[S][T])
            T=i;
    //cout<<S<<" "<<T<<endl;
    int L=(c[S][T]+c[0][S]+c[0][T])/2-c[0][T],
        R=(c[S][T]+c[0][S]+c[0][T])/2-c[0][S],
        K=(c[S][T]+c[0][S]+c[0][T])/2-c[S][T];
    int res=max(L,R);
    hub={L};
   // cout<<L<<" "<<R<<" "<<K<<endl;
    for(int i=1;i<n;i++)
        if(!(c[S][i]-c[0][i]>=L-K))
        //if(i==0)
        {
 
            int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
            //cout<<length<<endl;
           // cout<<i<<" "<<length<<" "<<dis[S][T]-length<<endl;
            if(res>max(length,c[S][T]-length))
                hub.clear();
            res=min(res,max(length,c[S][T]-length));
            if(max(length,c[S][T]-length)==res)
                hub.pb(length);
        }
    //cout<<hub.size()<<endl;
   // for(auto u:hub)cout<<u<<" ";cout<<endl;
    int kt=0;
  	while(hub.size()>1)
      hub.pop_back();
    for(auto cc:hub)
    {
        int cnt_l=0,cnt_r=0;
        for(int i=0;i<n;i++)
        {
            if(c[S][i]-c[0][i]==L-K)
            {
                cnt_r++;
                continue;
            }
            if(c[S][i]-c[0][i]>L-K)
            {
                //cout<<i<<" "<<(cc!=L)<<endl;
                if(cc!=L)
                    cnt_r++;
                continue;
            }
            int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
            if(length>cc)
            {
               // cout<<i<<endl;
                cnt_r++;
                continue;
            }
            if(length<cc)
            {
                cnt_l++;
                continue;
            }
        }
       // cout<<cnt_l<<" "<<cnt_r<<endl;
        if(cnt_l*2<=n&&cnt_r*2<=n&&(n-cnt_l-cnt_r)*2<=n)
            kt=1;
    }
    return res*(kt==0 ? -1 : 1);
}
 
#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n;
    int q;
    cin>>q;
    while(q--)
    {
        int n,sub;
        cin>>sub>>n;
        //cout<<n<<endl;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>dis[i][j];
        cout<<hubDistance(n, sub)<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:27:28: warning: unused parameter 'sub' [-Wunused-parameter]
   27 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

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