oj.uz

Submission #709474

# Submission time Handle Problem Language Result Execution time Memory
709474 2023-03-13T16:21:57 Z victor_gao Towns (IOI15_towns) C++17
100 / 100
 21 ms 980 KB 
#include "towns.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int mp[115][115];
int s,t,d; // 直徑兩端點
vector<int>up(115),ds(115);
int query(int a,int b){
	if (a==b) return 0;
	if (!mp[a][b]){
		int dis=getDistance(a,b);
		assert(dis!=0);
		mp[a][b]=dis;
		mp[b][a]=dis;
	}
	return mp[a][b];
}
bool check(int N,int dis){
	vector<int>to_mid(115,0),sz(115,0);
	for (int i=0;i<N;i++){
		if (ds[i]<dis) to_mid[i]=dis-ds[i]+up[i];
		else to_mid[i]=ds[i]-dis+up[i];
	}
	int num=1,alive=0;
	for (int i=1;i<N;i++){
		if (!num){
			sz[i]++; num=1; alive=i;
		}
		else {
			if (query(i,alive)==to_mid[i]+to_mid[alive]){
				sz[i]++; num--;
			}
			else num++,sz[alive]++;
		}
	}
	if (num<=0) return 1;
	num=0;
	for (int i=0;i<N;i++){
		if (!sz[i]) continue;
		if (query(i,alive)==to_mid[i]+to_mid[alive])
			num-=sz[i];
		else num+=sz[i];
	}
	return num<=0;
}
int hubDistance(int N, int sub) {
	for (int i=0;i<=N;i++){
		for (int j=0;j<=N;j++)
			mp[i][j]=0;
	}
	s=0; t=0; d=0;
	up.resize(N+1,0); ds.resize(N+1,0);
	d=-1;
	for (int i=1;i<N;i++){
		if (d<query(0,i)){
			d=query(0,i);
			s=i;
		}
	}
	d=-1;
	for (int i=0;i<N;i++){
		if (d<query(s,i)){
			d=query(s,i);
			t=i;
		}
	}
	up[s]=0; up[t]=0;
	int ans=1e9,sz=0,op=-1;
	map<pii,int>cnt;
	for (int i=0;i<N;i++){
		int a=query(0,s);
		int b=query(0,i);
		int c=query(i,s);
		up[i]=(b-a+c)/2;
		ds[i]=c-up[i];
		ans=min(ans,max(d-ds[i],ds[i]));
		cnt[{ds[i],d-ds[i]}]++;
	}
	int sol=0;
	for (auto [i,c]:cnt){
		if (max(i.x,i.y)==ans){
			if (sz<=N/2&&c<=N/2&&(N-c-sz)<=N/2){
				op=1; sol=0;
				break;
			}
			else if (sz<=N/2&&(N-c-sz)<=N/2){
				sol=i.x;
			}
		}
		sz+=c;
	}
	if (sol!=0){
		bool flag=check(N,sol);
		if (flag) op=1;
	}
	return ans*op;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:28: warning: unused parameter 'sub' [-Wunused-parameter]
   48 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 980 KB Output is correct
2 Correct 12 ms 828 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 14 ms 888 KB Output is correct
5 Correct 14 ms 824 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 404 KB Output is correct
2 Correct 21 ms 880 KB Output is correct
3 Correct 13 ms 888 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 424 KB Output is correct
2 Correct 15 ms 828 KB Output is correct
3 Correct 13 ms 824 KB Output is correct