oj.uz

Submission #387509

# Submission time Handle Problem Language Result Execution time Memory
387509 2021-04-08T15:57:32 Z alishahali1382 Towns (IOI15_towns) C++14
100 / 100
 24 ms 492 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto abcd_:abcd) cerr<<abcd_<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const int N=120;

int n, m, k, ans, X, Y;
int D[N][N], pref[N], suff[N];
vector<int> path, vec[N];

int ask(int i, int j){
	if (i==j) return 0;
	if (i>j) swap(i, j);
	if (D[i][j]==-1) D[i][j]=getDistance(i, j);
	return D[i][j];
}
inline bool check(int u, int v){
	return (ask(X, u)+ask(0, v)-ask(X, 0)-ask(u, v)!=0);
}
int hubDistance(int n, int sub){
	memset(D, -1, sizeof(D));
	memset(pref, 0, sizeof(pref));
	memset(suff, 0, sizeof(suff));
	for (int i=0; i<N; i++) vec[i].clear();
	path.clear();
	X=0;
	Y=0;
	for (int i=1; i<n; i++) if (ask(0, i)>ask(0, X)) X=i;
	for (int i=1; i<n; i++) if (ask(X, i)>ask(X, Y)) Y=i;
	ans=inf;
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, 0)-ask(0, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		ans=min(ans, max(a, b));
		path.pb(a);
	}
	if (sub<=2) return ans;
	sort(all(path));
	path.resize(unique(all(path))-path.begin());
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, 0)-ask(0, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		vec[lower_bound(all(path), a)-path.begin()].pb(i);
	}
	// 2n-3 so far
	// debugv(path)
	int len=path.size()-1;
	pref[0]=suff[len]=1;
	for (int i=1; i<=len; i++) pref[i]=pref[i-1]+SZ(vec[i]);
	for (int i=len; ~i; i--) suff[i]=suff[i+1]+SZ(vec[i]);
	for (int i=1; i<len; i++) if (max(path[i], ask(X, Y)-path[i])==ans){
		// center at distance vec[i]
		// check for centroid
		if (pref[i-1]>n/2 || suff[i+1]>n/2) continue ;
		if (SZ(vec[i])<=n/2) return ans;
		if (sub==4) continue ;
		
		vector<int> shit, gooni;
		for (int u:vec[i]){
			if (shit.empty()) shit.pb(u);
			else if (check(shit.back(), u)) gooni.pb(u);
			else{
				shit.pb(u);
				if (gooni.size()){
					shit.pb(gooni.back());
					gooni.pop_back();
				}
			}
		}

		int v=shit.back(), ted=gooni.size();
		while (shit.size()){
			int u=shit.back();
			shit.pop_back();
			if (check(v, u)){
				ted++;
				if (shit.size()) shit.pop_back(); // not same as v
			}
		}
		if (ted<=n/2) return ans;
	}
	
	return -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:31:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   31 | int hubDistance(int n, int sub){
      |                               ^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n, m, k, ans, X, Y;
      |     ^
towns.cpp:44:22: warning: unused variable 'c' [-Wunused-variable]
   44 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:53:7: warning: unused variable 'b' [-Wunused-variable]
   53 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |       ^
towns.cpp:53:22: warning: unused variable 'c' [-Wunused-variable]
   53 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:58:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |  int len=path.size()-1;
      |          ~~~~~~~~~~~^~
towns.cpp:82:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   82 |   int v=shit.back(), ted=gooni.size();
      |                          ~~~~~~~~~~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 492 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 22 ms 364 KB Output is correct
5 Correct 22 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 364 KB Output is correct
2 Correct 17 ms 364 KB Output is correct
3 Correct 23 ms 364 KB Output is correct
4 Correct 22 ms 364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 23 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 23 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 364 KB Output is correct
2 Correct 23 ms 364 KB Output is correct
3 Correct 24 ms 364 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 364 KB Output is correct
2 Correct 22 ms 364 KB Output is correct
3 Correct 22 ms 364 KB Output is correct