제출 #798615

#제출 시각아이디문제언어결과실행 시간메모리
798615Username4132도시들 (IOI15_towns)C++14
100 / 100
14 ms1068 KiB
#include "towns.h" #include<iostream> #include<vector> #include<algorithm> using namespace std; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define PB push_back #define F first #define S second const int MAXN = 120; int n, dis, mx, v=-1, w=-1, d1[MAXN], d2[MAXN], hdi[MAXN]; inline int calc(int ver){ return (mx+d2[ver]-d1[ver])>>1; } inline bool check(int i, int j){ return getDistance(i, j) < hdi[i] + hdi[j]; } pii solve(vector<int>& vec, int l){ if(l==(int)vec.size()) return {-1, -1}; vector<int> eq, di; eq.PB(vec[l]); int cur=l+1; while(cur<(int)vec.size() && eq.size()!=di.size()){ if(check(vec[l], vec[cur])) eq.PB(vec[cur]); else di.PB(vec[cur]); ++cur; } if(eq.size()!=di.size()) return {vec[l], eq.size()}; pii val = solve(vec, cur); if(val.F==-1) return {-1, -1}; if(check(vec[l], val.F)) return {vec[l], val.S + eq.size()}; int cou=val.S; for(int el:di) cou+=check(el, val.F); if(2*cou>((int)vec.size())-l) return {val.F, cou}; else return {-1, -1}; } bool test(int d){ int x=0, y=0; vector<int> us; forn(i, n){ int nd = calc(i); if(nd>d) ++x; else if(nd<d) ++y; else us.PB(i); } if(x>(n/2) || y>(n/2)) return false; for(int el:us) hdi[el]=d2[el]-calc(el); pii ret = solve(us, 0); return ret.S<=(n/2); } int hubDistance(int N, int sub) { n=N; forn(i, n) d1[i]=d2[i]=0; mx=-1; forsn(i, 1, n){ d1[i]=getDistance(0, i); if(mx<d1[i]) mx=d1[i], v=i; } dis=-1; forn(i, n) if(i!=v){ d2[i]=getDistance(v, i); if(dis<d2[i]) dis=d2[i], w=i; } int cc = calc(w); int ans = 1000000000; forn(i, n){ int d = calc(i); if(d<=cc) ans = min(ans, max(d, dis-d)); } vector<int> used; bool yes=false; forn(i, n){ int d = calc(i); if(max(d, dis-d)==ans && find(used.begin(), used.end(), d)==used.end()) yes|=test(d), used.PB(d); } return (yes? ans : -ans); }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:59:28: warning: unused parameter 'sub' [-Wunused-parameter]
   59 | 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...