Submission #57807

#	Time	Username	Problem	Language	Result	Execution time	Memory
57807		alenam0161	Towns (IOI15_towns)	C++17	25 / 100	49 ms	1492 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

int f[1107][1107];
int d[1107][1107];
int hubDistance(int N, int sub) {
  	for(int i=0;i<N;++i)
        for(int j=0;j<N;++j){
            f[i][j]=0;
        }
  	auto  dis=[&](int x,int y){
          if(x==y)return 0;
          if(x>y)swap(x,y);
          if(f[x][y]==false){
              f[x][y]=true;
              d[x][y]=getDistance(x,y);
          }
        return d[x][y];
    };
	int x=-1;
	for(int i=1;i<N;++i){
        if(x==-1||dis(0,x)<dis(0,i)){
            x=i;
        }
	}
	int y=-1;
	for(int i=0;i<N;++i){
        if(y==x)continue;
        if(i==x)continue;
        if(y==-1||dis(x,y)<dis(x,i)){
            y=i;
        }
	}
	map<int,int> mp;
	map<int,vector<int>> qan;
	for(int i=0;i<N;++i){
        if(i==x||i==y){
            continue;
        }
        int d1=dis(x,i);
        int d2=dis(y,i);
        int l=dis(x,y);
        int e=d1+d2-l;
        e/=2;
        int v=d2-e;
        mp[v]=max(mp[v],e);
        mp[v]=max(mp[v],d1-e);
        mp[v]=max(mp[v],d2-e);
        qan[v].push_back(i);
	}
	
	int ans=1e9;
	int hwx=1;
	bool ok=false;
	int hx=(N)/2;
	int hwl=1;
	int b=0;
	for(auto it=mp.begin();it!=mp.end();++it){
        ans=min(ans,it->second);
        int ds=it->first;
        int oth=qan[ds].size();
        int r=N-hwl-oth;
        if(r>hx||hwl>hx){

        }
        else if(oth>hx){
            b=hx;
            if(qan[ds].size()>hx){
                for(int j=1;b>0;j++,b--){
                    if(j>=qan[ds].size())break;
                    int len=dis(qan[ds][j],qan[ds][0]);
                    int l1=dis(qan[ds][j],y)+dis(qan[ds][j],x)-dis(x,y);
                    int l2=dis(qan[ds][0],y)+dis(qan[ds][0],x)-dis(x,y);
                    l1/=2;
                    l2/=2;
                    if(l1+l2 == len){
                        oth--;
                    }
                }
                if(oth<=hx)ok=true;
            }
            else{
                ok=true;
            }
        }
        else {
        ok=true;
        }

        hwl+=oth;
	}
	return ans*(ok==true ? 1:-1);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:63:29: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         int oth=qan[ds].size();
                 ~~~~~~~~~~~~^~
towns.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(qan[ds].size()>hx){
                ~~~~~~~~~~~~~~^~~
towns.cpp:72:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(j>=qan[ds].size())break;
                        ~^~~~~~~~~~~~~~~~
towns.cpp:55:6: warning: unused variable 'hwx' [-Wunused-variable]
  int hwx=1;
      ^~~
towns.cpp:8:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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