oj.uz

Submission #788140

# Submission time Handle Problem Language Result Execution time Memory
788140 2023-07-19T20:10:26 Z GusterGoose27 Towns (IOI15_towns) C++17
61 / 100
 13 ms 656 KB 
#include "towns.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 120;
const int inf = 1e9;
int uf[MAXN];
int sz[MAXN];
bool matched[MAXN];
int cache[MAXN][MAXN];
int paired[MAXN];
int diam;
int n;
int amt;
int l, r;

void reset(int sub) {
	if (sub == 1) amt = n*(n-1)/2;
	if (sub == 2) amt = (7*n+1)/2;
	if (sub == 3) amt = n*(n-1)/2;
	if (sub == 4) amt = (7*n+1)/2;
	if (sub == 5) amt = 5*n;
	if (sub == 6) amt = (7*n+1)/2;
	iota(uf, uf+n, 0);
	fill(sz, sz+n, 1);
	fill(matched, matched+n, 0);
	for (int i = 0; i < n; i++) fill(cache[i], cache[i]+n, 0);
	// paired, ignore
}

int _abs(int a) {
	return a < 0 ? -a : a;
}

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void merge(int i, int j) {
	i = find(i);
	j = find(j);
	assert(i != j);
	uf[i] = j;
	sz[j] += sz[i];
}

int getdist(int i, int j) {
	assert(i >= 0 && j >= 0 && i < n && j < n);
	if (i == j) return 0;
	if (cache[i][j] == 0) {
		assert(amt);
		cache[i][j] = cache[j][i] = getDistance(i, j);
		amt--;
	}
	return cache[i][j];
}

bool same(int i, int j) {
	return getdist(l, i)+getdist(i, r)+getdist(j, l)+getdist(j, r) != 2*diam+2*getdist(i, j);
}

void permute(vector<int> &v) {
	mt19937 gen(1);
	for (int i = 1; i < v.size(); i++) {
		swap(v[i], v[gen()%(i+1)]);
	}
}

bool valid(vector<int> &vals) {
	if (vals.size() <= n/2) return 1;
	permute(vals);
	int m = vals.size();
	int ex = -1;
	for (int i = 0; i < m; i++) {
		if (matched[i]) continue;
		bool f = 0;
		for (int _ = i+1; _ < m+i; _++) {
			int j = _%m;
			if (matched[j] || find(i) == find(j)) continue;
			if (same(vals[i], vals[j])) {
				merge(i, j);
			}
			else {
				matched[i] = matched[j] = 1;
				paired[i] = j;
				paired[j] = i;
				f = 1;
				break;
			}
			if (sz[find(i)] > n/2) return 0;
		}
		if (!f) {
			ex = i;
			break;
		}
	}
	if (ex == -1) return 1;
	for (int i = 0; i < m; i++) {
		if (sz[find(ex)] > n/2) return 0;
		if (find(i) == find(ex)) {
			continue;
		}
		assert(matched[i]);
		if (find(paired[i]) == find(ex)) continue;
		if (same(vals[i], vals[ex])) {
			merge(i, ex);
			continue;
		}
	}
	return sz[find(ex)] <= n/2;
}

int hubDistance(int N, int sub) {
	n = N;
	reset(sub);
	l = 0;
	int d = 0;
	for (int i = 1; i < n; i++) {
		int cur = getdist(0, i);
		if (cur > d) {
			l = i;
			d = cur;
		}
	}
	r = 0;
	for (int i = 1; i < n; i++) {
		int v = getdist(i, l);
		if (v > getdist(l, r)) r = i;
	}
	int mn = inf;
	for (int i = 0; i < n; i++) {
		mn = min(mn, _abs(getdist(l, i)-getdist(i, r)));
	}
	// return (mn+dist[r][0])/2;
	vector<int> cont[4];
	for (int i = 0; i < n; i++) {
		int diff = getdist(i, r)-getdist(l, i);
		if (diff > mn) cont[0].push_back(i);
		else if (diff == mn) cont[1].push_back(i);
		else if (diff == -mn) cont[2].push_back(i);
		else cont[3].push_back(i);
	}
	diam = getdist(l, r);
	int R = (diam+mn)/2;
	if (sub < 3) return R;
	if (cont[1].size() && (cont[0].size()+cont[1].size() >= cont[2].size()+cont[3].size())) {
		if (cont[0].size() > n/2 || !valid(cont[1])) return -R;
		return R;
	}
	if (cont[2].size() && (cont[0].size()+cont[1].size() <= cont[2].size()+cont[3].size())) {
		if (cont[3].size() > n/2 || !valid(cont[2])) return -R;
		return R;
	}
	return -R;
}

Compilation message

towns.cpp: In function 'void permute(std::vector<int>&)':
towns.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
towns.cpp: In function 'bool valid(std::vector<int>&)':
towns.cpp:72:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  if (vals.size() <= n/2) return 1;
      |      ~~~~~~~~~~~~^~~~~~
towns.cpp:74:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   74 |  int m = vals.size();
      |          ~~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:149:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |   if (cont[0].size() > n/2 || !valid(cont[1])) return -R;
      |       ~~~~~~~~~~~~~~~^~~~~
towns.cpp:153:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  153 |   if (cont[3].size() > n/2 || !valid(cont[2])) return -R;
      |       ~~~~~~~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 596 KB Output is correct
2 Correct 9 ms 544 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 13 ms 612 KB Output is correct
5 Correct 12 ms 596 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 644 KB Output is correct
2 Correct 9 ms 632 KB Output is correct
3 Correct 13 ms 596 KB Output is correct
4 Correct 13 ms 576 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 656 KB Output is correct
2 Correct 13 ms 552 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 13 ms 652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 636 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 13 ms 536 KB Output is correct
3 Correct 13 ms 548 KB Output is correct

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -