제출 #71622

#제출 시각아이디문제언어결과실행 시간메모리
71622Sa1378도시들 (IOI15_towns)C++17
26 / 100
36 ms5304 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; #define N ((int)230) int dis[N],dis2[N],dis3[N]; map <int,vector <int> > mp[2]; bool mark[N]; int hubDistance(int n, int sub) { mp[0].clear();mp[1].clear(); int id=0,maxi=0; for(int i=1;i<n;i++) { int ex=getDistance(0,i); if(ex>maxi)maxi=ex,id=i; } dis[0]=maxi;dis[id]=0; int id2=0; for(int i=1;i<n;i++) if(i!=id) { dis[i]=getDistance(id,i); if(dis[i]>maxi)maxi=dis[i],id2=i; } dis2[id]=maxi;dis2[id2]=0; for(int i=0;i<n;i++) if(i!=id && i!=id2) dis2[i]=getDistance(id2,i); int R=(int)1e9; int cnt0=0; for(int i=0;i<n;i++) { bool p=(dis[i]>dis2[i]); if(p==0)cnt0++; int ex=(dis2[id]+abs(dis2[i]-dis[i]))/2; R=min(R,ex); mp[p][ex].push_back(i); } vector <int> vec; int x0=mp[0].begin()->first,x1=mp[1].begin()->first; if(x0==R && x1==R) { if(cnt0<=n/2) { vec=mp[1].begin()->second; if(n-cnt0-(int)vec.size()>n/2)return -R; } else { vec=mp[0].begin()->second; if(cnt0-(int)vec.size()>n/2)return -R; } } else if(x0==R) { vec=mp[0].begin()->second; if(n-cnt0>n/2 || cnt0-(int)vec.size()>n/2)return -R; } else { vec=mp[1].begin()->second; if(cnt0>n/2 || n-cnt0-(int)vec.size()>n/2)return -R; } if(vec.size()<=n/2)return R; memset(mark,0,sizeof mark); for(auto u:vec) dis3[u]=(dis[u]+dis2[u]-dis2[id])/2; for(auto u:vec) { if(mark[u])continue; int cnt=1;mark[u]=1; for(auto v:vec) if(!mark[v] && getDistance(u,v)!=dis3[u]+dis3[v]) mark[v]=1,cnt++; if(cnt>n/2)return -R; } return R; }

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vec.size()<=n/2)return R;
     ~~~~~~~~~~^~~~~
towns.cpp:10: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...