Submission #206060

#TimeUsernameProblemLanguageResultExecution timeMemory
206060SegtreeTowns (IOI15_towns)C++14
25 / 100
46 ms4344 KiB
#include"towns.h" #include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define all(x) x,begin(),x.end() #define rep(i,n) for(int i=0;i<n;i++) #define mod 1000000007 #define mad(a,b) a=(a+b)%mod #define X 1000010 int cnts[X]; int hubDistance(int N,int SUBTASK){ int ma=0,A=-1; for(int i=0;i<N;i++){ int res=getDistance(0,i); if(res>ma)ma=res,A=i; } int dista[110]; ma=0; int B=-1; for(int i=0;i<N;i++){ int res=getDistance(A,i); dista[i]=res; if(res>ma)ma=res,B=i; } int distb[110]; for(int i=0;i<N;i++){ int res=getDistance(B,i); distb[i]=res; } rep(i,X)cnts[i]=0; set<ll> S; int ab=dista[B]; int ans=1e9; for(int i=0;i<N;i++){ int ax=dista[i],bx=distb[i]; int q=(ax+bx-ab)/2; int p=ax-q; int r=bx-q; chmin(ans,max(p,r)); S.insert(p); cnts[p]++; //cout<<i<<":"<<ax<<" "<<bx<<" "<<p<<" "<<q<<" "<<r<<endl; } ll U,V=-1; ll rui=0; for(auto t:S){ rui+=cnts[t]; if(rui>N/2){ U=t; break; } } rui=0; for(auto t:S){ rui+=cnts[t]; if(rui==N/2){ V=t; break; } } bool th=0; if(ans==max(U,ab-U))th=1; if(ans==max(V,ab-V)&&V>=0)th=1; if(th==0)ans*=-1; return ans; }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:27: warning: unused parameter 'SUBTASK' [-Wunused-parameter]
 int hubDistance(int N,int SUBTASK){
                           ^~~~~~~
towns.cpp:69:18: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(ans==max(U,ab-U))th=1;
                ~~^~
#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...