Submission #599393

#	Time	Username	Problem	Language	Result	Execution time	Memory
599393		Temmie	Towns (IOI15_towns)	C++17	25 / 100	16 ms	980 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

struct Dsu {
	std::vector <int> p;
	Dsu (int s) {
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
	}
	int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	void unite(int u, int v) {
		p[find(u)] = find(v);
	}
	void print() {
		for (int i = 0; i < (int) p.size(); i++) std::cerr << find(i) << " ";
		std::cerr << std::endl;
	}
};

std::vector <std::vector <int>> mem;

int ask(int i, int j) {
	if (i == j) return 0;
	if (mem[i][j]) return mem[i][j];
	if (mem[j][i]) return mem[j][i];
	return mem[i][j] = mem[j][i] = getDistance(i, j);
}

int hubDistance(int n, int sub) {
	mem = std::vector <std::vector <int>> (n, std::vector <int> (n, 0));
	int l1, l2;
	int mx = 0;
	for (int i = 1; i < n; i++) {
		int val = ask(0, i);
		if (val > mx) {
			mx = val;
			l1 = i;
		}
	}
	std::vector <int> dl1(n, -1);
	std::vector <int> dl2(n, -1);
	mx = 0;
	for (int i = 0; i < n; i++) {
		if (i == l1) {
			continue;
		}
		dl1[i] = ask(l1, i);
		if (dl1[i] > mx) {
			mx = dl1[i];
			l2 = i;
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == l2) {
			continue;
		}
		dl2[i] = ask(l2, i);
	}
	int r = 1 << 30;
	std::vector <int> to(n);
	int xx, yy;
	for (int i = 0; i < n; i++) {
		if (i == l1 || i == l2) {
			continue;
		}
		to[i] = (dl1[i] + dl2[i] - dl1[l2]) / 2;
		int x = (dl1[l2] + dl1[i] - dl2[i]) / 2;
		int y = (dl2[l1] + dl2[i] - dl1[i]) / 2;
		if (std::max(x, y) < r) {
			xx = x;
			yy = y;
			r = std::max(x, y);
		}
	}
	if (sub <= 2) {
		return r;
	}
	to[l1] = xx;
	to[l2] = yy;
	std::vector <bool> vis(n, false);
	Dsu dsu(n);
	vis[l1] = vis[l2] = true;
	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		bool is = true;
		is &= to[l1] != ask(l1, i) - to[i];
		is &= to[l2] != ask(l2, i) - to[i];
		if (is) {
			//std::cerr << i << " is" << std::endl;
			vis[i] = true;
			int vl1 = ask(l1, i) - to[i];
			if (vl1 > to[l1]) {
				dsu.unite(l2, i);
			} else {
				dsu.unite(l1, i);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (vis[i] || vis[j]) {
				continue;
			}
			if (ask(i, j) != to[i] + to[j]) {
				dsu.unite(i, j);
			}
		}
	}
	std::vector <int> siz(n, 0);
	int max = 0;
	for (int i = 0; i < n; i++) {
		max = std::max(max, ++siz[dsu.find(i)]);
	}
	//dsu.print();
	//std::cerr << "n = " << n << " ; max = " << max << std::endl;
	if (max <= n / 2) return r;
	return -r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:80:9: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |  to[l1] = xx;
towns.cpp:81:9: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |  to[l2] = yy;
towns.cpp:59:15: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |   dl2[i] = ask(l2, i);
      |            ~~~^~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39