oj.uz

Submission #617011

# Submission time Handle Problem Language Result Execution time Memory
617011 2022-08-01T08:12:52 Z Lucpp Towns (IOI15_towns) C++17
100 / 100
 19 ms 852 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())

int hubDistance(int n, int sub) {
	sub--; // suppress unused warning
	vector<int> d0(n), du(n);
	for(int i = 1; i < n; i++) d0[i] = getDistance(0, i);
	int u = int(max_element(d0.begin(), d0.end())-d0.begin());
	for(int i = 0; i < n; i++) if(u!=i) du[i] = getDistance(u, i);
	int v = int(max_element(du.begin(), du.end())-du.begin());
	int l = 0, r = 0;
	vector<int> xl, xr;
	int maxB = 0, maxC = 0;
	for(int i = 0; i < n; i++){
		int b = (d0[u]+d0[i]-du[i])/2;
		int c = d0[u]-b;
		if(b+du[v]-d0[u] <= du[v]/2){
			if(b < maxB) l++;
			if(b > maxB) l+=sz(xl), xl.clear(), maxB = b;
			if(b == maxB) xl.push_back(i);
		}
		if(c <= du[v]/2){
			if(c < maxC) r++;
			if(c > maxC) r+=sz(xr), xr.clear(), maxC = c;
			if(c == maxC) xr.push_back(i);
		}
	}
	int R = min(d0[u]-maxB, du[v]-maxC);
	vector<int> x;
	bool ok = false;
	// cerr << maxB << " " << maxC << " " << l << " " << r << " " << sz(xl) << " " << sz(xr) << "\n";
	if(d0[u]-maxB == R){
		if(l <= n/2 && r+sz(xr) <= n/2) x = xl, ok = true;
	}
	if(du[v]-maxC == R){
		if(l+sz(xl) <= n/2 && r <= n/2) x = xr, ok = true;
	}
	if(xl == xr){
		if(l <= n/2 && r <= n/2) x = xl, ok = true;
	}
	if(!ok) return -R;
	auto same = [&](int a, int b){
		return getDistance(a, b) < (d0[a]+du[a]-d0[u])/2 + (d0[b]+du[b]-d0[u])/2;
	};
	vector<int> cache(sz(x), -1);
	int cnt = 1;
	int cur = 0;
	cache[0] = 0;
	for(int i = 1; i < sz(x); i++){
		if(same(x[cur], x[i])) cnt++, cache[i] = cur;
		else if(--cnt == 0){
			cur = i;
			cnt = 1;
			cache[i] = cur;
		}
	}
	int other = 0;
	bool isSame = false;
	for(int i = 0; i < sz(x); i++){
		// cerr << cache[i] << "\n";
		if(other >= (n+1)/2) break;
		if(cache[i] == i){
			if(isSame) isSame = false;
			else isSame = same(x[cur], x[i]);
		}
		if(cache[i] != -1 && !isSame) other++;
		if(cache[i] == -1 && isSame) other++;
		if(cache[i] == -1 && !isSame) other += !same(x[cur], x[i]);
	}
	if(sz(x)-other <= n/2) return R;
	else return -R;
}

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 352 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 12 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 10 ms 360 KB Output is correct
3 Correct 13 ms 340 KB Output is correct
4 Correct 13 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 15 ms 832 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 828 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 9 ms 340 KB Output is correct
2 Correct 18 ms 848 KB Output is correct
3 Correct 14 ms 844 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 19 ms 840 KB Output is correct
3 Correct 13 ms 852 KB Output is correct