Submission #705977

#	Time	Username	Problem	Language	Result	Execution time	Memory
705977		bin9638	Towns (IOI15_towns)	C++17	25 / 100	16 ms	532 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 dem,dis[N][N],c[N][N],S,T,L,R,K;

#ifdef SKY
int getDistance(int i, int j)
{
    dem++;
    return dis[i][j];
}
#endif // SKY

bool cung_phia(int u,int v,int hub)
{
    c[u][v]=c[v][u]=getDistance(u,v);
    //cout<<L<<" "<<R<<" "<<K<<" "<<c[S][u]-c[0][u]<<" "<<L-K<<endl;
    if(c[S][u]-c[0][u]>L-K||c[S][v]-c[0][v]>L-K)
        return(c[S][u]-c[0][u]>L-K&&c[S][v]-c[0][v]>L-K);
    int length_u=(c[S][u]-c[0][u]==L-K ? L : (c[S][u]+c[0][u]+c[0][S])/2-c[0][u]),
        length_v=(c[S][v]-c[0][v]==L-K ? L : (c[S][v]+c[0][v]+c[0][S])/2-c[0][v]);
    if(length_u!=length_v)
        return(hub<min(length_u,length_v)||hub>max(length_u,length_v));
    if(length_u!=hub)
        return 1;
    return(!(hub*2+c[u][v]==c[S][u]+c[S][v]));
}

bool check(int hub,int n)
{
 //   cout<<cung_phia(10,0,hub)<<endl;
    stack<int>bucket,lis;
    lis.push(0);
    for(int i=1;i<n;i++)
        if(cung_phia(lis.top(),i,hub))
        {//cung nhom
           // cout<<i<<" "<<lis.top()<<endl;
            bucket.push(i);
        }else
        {
            lis.push(i);
            if(!bucket.empty())
            {
                lis.push(bucket.top());
                bucket.pop();
            }
        }
    //cout<<dem<<endl;
    //cout<<lis.size()<<endl;
    int val=lis.top();
  //  cout<<val<<endl;
    while(!lis.empty())
    {
        //cout<<"cc\n";
        if(bucket.empty())
            return 0;
        if(cung_phia(val,lis.top(),hub))
        {
           // cout<<lis.size()<<endl;
            for(int i=1;i<=2;i++)
                if(!lis.empty())
                    lis.pop();
        }else
        {
            //cout<<lis.size()<<endl;
            lis.pop();
            bucket.pop();
        }
       // cout<<lis.size()<<endl;
        if(bucket.empty())
            return 0;
    }
    return 1;
}

int hubDistance(int n, int sub)
{
    memset(c,0,sizeof(c));
    dem=0;
    for(int i=1;i<n;i++)
        c[0][i]=c[i][0]=getDistance(0,i);
     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);
     T=0;
    for(int i=0;i<n;i++)
        if(c[S][i]>c[S][T])
            T=i;
        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);
   // cout<<S<<" "<<T<<" "<<L<<" "<<R<<" "<<K<<endl;
    vector<int>hub={L};
    for(int i=1;i<n;i++)
        if(!(c[S][i]-c[0][i]>=L-K))
        {
            int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
      //      cout<<i<<" "<<length<<" "<<c[S][i]-c[0][i]<<" "<<L-K<<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);
        }
    sort(hub.begin(),hub.end());
    hub.erase(unique(hub.begin(),hub.end()),hub.end());
   // for(auto cc:hub)cout<<cc<<" ";cout<<endl;
    //for(int i=0;i<n;i++)
     //   for(int j=0;j<i;j++)
       //     if(cung_phia(i,j,hub[0]))cout<<i<<" "<<j<<endl;
   //  cout<<dem<<endl;
    if(hub.size()==1)
        return res*(check(hub[0],n)==1 ? -1 : 1);
    int cnt=0;
    for(int i=1;i<n;i++)
        if(!(c[S][i]-c[0][i]>=L-K))
        {
            int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
            if(length<hub[1])
                cnt++;
        }
    if(cnt*2<=n)
        return res*(check(hub[1],n)==1 ? -1 : 1);
    return res*(check(hub[0],n)==1 ? -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;
        cout<<dem<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:103:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  103 |     for(int i=0;i<n;i++)
      |     ^~~
towns.cpp:106:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |         L=(c[S][T]+c[0][S]+c[0][T])/2-c[0][T],
      |         ^
towns.cpp:88:28: warning: unused parameter 'sub' [-Wunused-parameter]
   88 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

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