oj.uz

Submission #379646

# Submission time Handle Problem Language Result Execution time Memory
379646 2021-03-19T01:05:01 Z crackersamdjam Towns (IOI15_towns) C++17
100 / 100
 28 ms 1132 KB 
#include "towns.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
template<typename T> int size(T &x){return (int)x.size();}

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;

int hubDistance(int n, int sub){
	int lim = (7*n+1)/2;
	map<pair<int, int>, int> mp;
	auto getdis = [&](int x, int y){
		if(x == y) return 0;
		if(x > y) swap(x, y);
		if(mp[{x, y}]) return mp[{x, y}];
		lim--;
		assert(lim >= 0);
		return mp[{x, y}] = getDistance(x, y);
	};

	vector<int> dis0(n), diss(n);
	dis0[0] = 0;
	int s = 0;
	for(int i = 0; i < n; i++){
		dis0[i] = getdis(0, i);
		if(dis0[i] > dis0[s])
			s = i;
	}
	diss[s] = 0;
	diss[0] = dis0[s];
	vector<int> cc(n), bb(n), aa(n);
	int t = 0;

	for(int i = 0; i < n; i++){
		diss[i] = getdis(s, i);
		//use previous to calculate this
		// a + b = dis0[s]
		// a + c = dis0[i]
		// b + c = diss[i]
		// 
		// diss[i]+dis0[i]-dis0[s] = 2c
		int c = diss[i]+dis0[i]-dis0[s];
		// assert(c%2 == 0);
		c /= 2;
		aa[i] = dis0[i]-c;
		bb[i] = diss[i]-c;
		cc[i] = c;

		if(diss[i] > diss[t])
			t = i;
	}

	int dia = diss[t];

	auto val = [&](int x){
		return max(x, dia-x);
	};

	int best = dia;
	
	for(int i = 0; i < n; i++){
		// this distance works since path 0 to s passes centre
		int d = diss[i]-cc[i];
		if(val(d) < val(best)){
			best = d;
		}
	}

	int ans = val(best), second = -1;
	for(int i = 0; i < n; i++){
		int d = diss[i]-cc[i];
		if(d == dia-best)
			second = d;
	}

	auto centval = [&](int val){
		int ls = 0, rs = 0;
		for(int i = 0; i < n; i++){
			int d = bb[i];
			if(d == val);
			else if(d > val)
				ls++;
			else if(d < val)
				rs++;
		}
		return max(ls, rs);
	};

	//there may be two centres
	if(second != -1 and val(second) == val(best) and centval(second) < centval(best))
		best = second;

	vector<int> v;
	int ls = 0, rs = 0;
	for(int i = 0; i < n; i++){
		int d = bb[i];
		if(d == best){
			v.emplace_back(i);
		}
		else if(d > best)
			ls++;
		else if(d < best)
			rs++;
	}

	if(max(ls, rs) > n/2)
		return -ans;

	vector<array<int, 3>> cur, rest;
	for(int i: v)
		cur.push_back({i, 1, 1});

	while(size(cur) > 1){
		vector<array<int, 3>> nx;
		for(int i = 0; i < size(cur); i += 2){
			if(i == size(cur)-1){
				nx.emplace_back(cur[i]);
				continue;
			}
			auto a = cur[i], b = cur[i+1];
			
			int longd = cc[a[0]]+cc[b[0]];
			int reald = getdis(a[0], b[0]);
			// assert(reald <= longd);

			if(reald < longd){
				nx.push_back({a[0], a[1]+b[1], a[2]+b[2]});
			}
			else{
				if(a[1] > b[1]){
					nx.push_back({a[0], a[1]-b[1], a[2]});
					rest.push_back(b);
				}
				else if(a[1] < b[1]){
					nx.push_back({b[0], b[1]-a[1], b[2]});
					rest.push_back(a);
				}
				else{
					rest.push_back(a);
					rest.push_back(b);
				}
			}
		}
		cur = nx;
	}
	if(sub > 2 and size(cur)){
		// assert(size(cur) == 1);
		int a = cur[0][0], yes = cur[0][2];
		for(auto [b, _, sz]: rest){
			int longd = cc[a]+cc[b];
			int reald = getdis(a, b);
			// assert(reald <= longd);
			if(reald < longd){
				yes += sz;
			}
		}
		if(yes > n/2)
			return -ans;
	}

	return ans;
}

Compilation message

towns.cpp: In lambda function:
towns.cpp:85:28: warning: declaration of 'val' shadows a previous local [-Wshadow]
   85 |  auto centval = [&](int val){
      |                            ^
towns.cpp:64:7: note: shadowed declaration is here
   64 |  auto val = [&](int x){
      |       ^~~

Subtask #1
13.0 / 13.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1004 KB Output is correct
2 Correct 21 ms 876 KB Output is correct
3 Correct 22 ms 876 KB Output is correct
4 Correct 22 ms 876 KB Output is correct

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1132 KB Output is correct

Subtask #5
13.0 / 13.0

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

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1024 KB Output is correct
2 Correct 23 ms 940 KB Output is correct
3 Correct 22 ms 876 KB Output is correct