oj.uz

Submission #677146

# Submission time Handle Problem Language Result Execution time Memory
677146 2023-01-02T12:12:34 Z jamezzz Towns (IOI15_towns) C++17
100 / 100
 16 ms 948 KB 
#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 vector<int> vi;
typedef pair<int,int> ii;

int cnt,n;
map<int,int> memo[150];

inline int ask(int a,int b){
	if(a==b)return 0;
	if(memo[a].find(b)!=memo[a].end())return memo[a][b];
	++cnt;
	assert(cnt<7*n/2);
	return memo[a][b]=memo[b][a]=getDistance(a,b);
}

int hubDistance(int N,int sub){
	n=N;
	cnt=0;
	for(int i=0;i<N;++i)memo[i].clear();
	
	int a=0,b=0,diam=0;
	for(int i=0;i<N;++i)if(ask(a,i)>ask(a,b))b=i;
	for(int i=0;i<N;++i)diam=max(diam,ask(b,i));
	
	int ans=diam;
	
	vector<ii> v;
	for(int i=0;i<N;++i){
		int ab=ask(a,b),ai=ask(a,i),bi=ask(i,b);
		int db=(ab+bi-ai)/2;
		v.pb({db,i});
		ans=min(ans,max(db,diam-db));
	}
	sort(all(v));
	
	/*
	pf("diam: %d\n",diam);
	pf("v: ");
	for(auto[a,b]:v)pf("{%d %d} ",a,b);
	pf("\n");
	*/
	
	for(int i=0;i<N;++i){
		//pf("%d\n",i);
		if(max(v[i].fi,diam-v[i].fi)!=ans)continue;
		int l=i,r=i;
		while(r<N-1&&v[r].fi==v[r+1].fi)++r;
		//pf("%d %d %d %d\n",i,l,r,N);
		if(l>N/2||N-r-1>N/2)continue;
		
		vector<vi> cur,nxt,dead;
		for(int i=l;i<=r;++i)cur.pb({v[i].se});
		
		//pf("l: %d, r: %d\n",l,r);
		
		vi rep={};
		while(!cur.empty()){
			
			/*
			pf("cur: ");
			for(vi x:cur){
				pf("{");
				for(int i:x)pf("%d ",i);
				pf("} ");
			}
			pf("\n");
			*/
			
			for(int i=0;i<sz(cur);i+=2){
				if(i+1==sz(cur)){
					if(!rep.empty())dead.pb(rep);
					rep=cur[i];
				}
				else{
					int x=cur[i][0],y=cur[i+1][0];
					if(ask(b,x)+ask(b,y)-ask(x,y)>2*v[l].fi){
						vi tmp;
						for(int x:cur[i])tmp.pb(x);
						for(int x:cur[i+1])tmp.pb(x);
						nxt.pb(tmp);
					}
					else dead.pb(cur[i]),dead.pb(cur[i+1]);
				}
			}
			swap(cur,nxt);
			nxt.clear();
		}
		
		if(rep.empty())return ans;
		
		int num=sz(rep);
		for(vi i:dead){
			int x=rep[0],y=i[0];
			if(ask(b,x)+ask(b,y)-ask(x,y)>2*v[l].fi)num+=sz(i);
		}
		//pf("num: %d\n",num);
		if(num<=N/2)return ans;
		
		i=r;
	}
	
	return -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:61:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   61 |   for(int i=l;i<=r;++i)cur.pb({v[i].se});
      |           ^
towns.cpp:52:10: note: shadowed declaration is here
   52 |  for(int i=0;i<N;++i){
      |          ^
towns.cpp:78:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   78 |    for(int i=0;i<sz(cur);i+=2){
      |            ^
towns.cpp:52:10: note: shadowed declaration is here
   52 |  for(int i=0;i<N;++i){
      |          ^
towns.cpp:87:15: warning: declaration of 'x' shadows a previous local [-Wshadow]
   87 |       for(int x:cur[i])tmp.pb(x);
      |               ^
towns.cpp:84:10: note: shadowed declaration is here
   84 |      int x=cur[i][0],y=cur[i+1][0];
      |          ^
towns.cpp:88:15: warning: declaration of 'x' shadows a previous local [-Wshadow]
   88 |       for(int x:cur[i+1])tmp.pb(x);
      |               ^
towns.cpp:84:10: note: shadowed declaration is here
   84 |      int x=cur[i][0],y=cur[i+1][0];
      |          ^
towns.cpp:101:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  101 |   for(vi i:dead){
      |          ^
towns.cpp:52:10: note: shadowed declaration is here
   52 |  for(int i=0;i<N;++i){
      |          ^
towns.cpp:25:27: warning: unused parameter 'sub' [-Wunused-parameter]
   25 | int hubDistance(int N,int sub){
      |                       ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 392 KB Output is correct
5 Correct 14 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 15 ms 396 KB Output is correct
4 Correct 14 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 15 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 392 KB Output is correct
2 Correct 16 ms 940 KB Output is correct
3 Correct 16 ms 948 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 408 KB Output is correct
2 Correct 15 ms 852 KB Output is correct
3 Correct 16 ms 912 KB Output is correct