Submission #676359

#	Time	Username	Problem	Language	Result	Execution time	Memory
676359		jamezzz	Towns (IOI15_towns)	C++17	25 / 100	20 ms	896 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

map<int,int> memo[150];

inline int ask(int a,int b){
	if(memo[a].find(b)!=memo[a].end())return memo[a][b];
	return memo[a][b]=memo[b][a]=getDistance(a,b);
}

int hubDistance(int N,int sub){
	for(int i=0;i<N;++i)memo[i].clear();
	
	int x=ask(0,1),y=ask(1,2),z=ask(0,2);
	int a=(x+z-y)/2;int b=x-a,c=z-a;
	vector<ii> v;
	v.pb({a,0});v.pb({b,1});v.pb({c,2});
	for(int i=3;i<N;++i){
		int y=ask(1,i),z=ask(0,i);
		int na=(x+z-y)/2;
		if(a<=na)v.pb({z-a,i});
		else v.pb({y-b,i});
	}
	
	//for(auto[x,y]:v)pf("%d %d\n",x,y);
	
	int mx=0,far=0;
	for(auto[d,i]:v){
		if(d>mx)mx=d,far=i;
	}
	
	int out,ans=mx;
	vector<int> l;
	vector<ii> r;
	for(auto[d,i]:v){
		int x=ask(i,far);
		if(x==d+mx)l.pb(d);
		else{
			r.pb({(d+mx-x)/2,d});
		}
	}
	sort(all(r),greater<ii>());
	
	//pf("ans: %d\n",ans);
	while(sz(r)!=1){
		//pf("l: ");for(int i:l)pf("%d ",i);pf("\n");
		//pf("r: ");for(auto[a,b]:r)pf("(%d %d) ",a,b);pf("\n");
		int cur=r.back().fi;
		//pf("cur: %d\n",cur);
		int mx=0;
		for(int i=0;i<sz(l);++i){
			l[i]+=cur;
			mx=max(mx,l[i]);
		}
		for(int i=0;i<sz(r);++i){
			r[i].fi-=cur;
			r[i].se-=cur;
			mx=max(mx,r[i].se);
		}
		while(r.back().fi==0){
			l.pb(r.back().se);
			r.pop_back();
		}
		//pf("l: ");for(int i:l)pf("%d ",i);pf("\n");
		//pf("r: ");for(auto[a,b]:r)pf("(%d %d) ",a,b);pf("\n");
		//pf("mx: %d\n",mx);
		if(ans>mx)ans=mx;
		else break;
	}
	
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:28:7: warning: declaration of 'y' shadows a previous local [-Wshadow]
   28 |   int y=ask(1,i),z=ask(0,i);
      |       ^
towns.cpp:23:17: note: shadowed declaration is here
   23 |  int x=ask(0,1),y=ask(1,2),z=ask(0,2);
      |                 ^
towns.cpp:28:18: warning: declaration of 'z' shadows a previous local [-Wshadow]
   28 |   int y=ask(1,i),z=ask(0,i);
      |                  ^
towns.cpp:23:28: note: shadowed declaration is here
   23 |  int x=ask(0,1),y=ask(1,2),z=ask(0,2);
      |                            ^
towns.cpp:45:7: warning: declaration of 'x' shadows a previous local [-Wshadow]
   45 |   int x=ask(i,far);
      |       ^
towns.cpp:23:6: note: shadowed declaration is here
   23 |  int x=ask(0,1),y=ask(1,2),z=ask(0,2);
      |      ^
towns.cpp:59:7: warning: declaration of 'mx' shadows a previous local [-Wshadow]
   59 |   int mx=0;
      |       ^~
towns.cpp:36:6: note: shadowed declaration is here
   36 |  int mx=0,far=0;
      |      ^~
towns.cpp:41:6: warning: unused variable 'out' [-Wunused-variable]
   41 |  int out,ans=mx;
      |      ^~~
towns.cpp:20:27: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | 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