Submission #57802

#TimeUsernameProblemLanguageResultExecution timeMemory
57802alenam0161Towns (IOI15_towns)C++17
25 / 100
40 ms1868 KiB
#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=0; 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())ok=true; int len=dis(qan[ds][j],qan[ds][0]); len=dis(qan[ds][j],y)-len; len/=2; if(len!=ds){ oth--; } } if(oth>hx)ok=true; } else{ ok=true; } } } return ans*(ok==false ? 1:-1); }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:62: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:69:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(qan[ds].size()>hx){
                ~~~~~~~~~~~~~~^~~
towns.cpp:71:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(j>=qan[ds].size())ok=true;
                        ~^~~~~~~~~~~~~~~~
towns.cpp:54: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) {
                            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...