oj.uz

Submission #749423

# Submission time Handle Problem Language Result Execution time Memory
749423 2023-05-28T03:00:47 Z Abrar_Al_Samit Towns (IOI15_towns) C++17
25 / 100
 14 ms 360 KB 
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

const int nax = 110;

int from0[nax];
int fromu[nax];
int c[nax];
int u, v;

bool EQUAL(int u, int v) {
	if(u==v) return true;

	int d = getDistance(u, v);
	return d != c[u]+c[v];
}
int Do_The_Majority_Thing(vector<int>v) {
	// http://www.cs.yale.edu/publications/techreports/tr252.pdf

	int n = v.size();

	vector<int>list, bucket;
	for(int i=0; i<n; ++i) {
		if(list.empty() || !EQUAL(list.back(), v[i])) {
			list.push_back(v[i]);
			if(!bucket.empty()) {
				list.push_back(bucket.back());
				bucket.pop_back();
			}
		} else {
			bucket.push_back(v[i]);
		}
	}

	int T = list.back();


	int cnt = 0;
	while(list.size()>1) {
		if(EQUAL(T, list.back())) {
			list.pop_back();
			list.pop_back();
		} else {
			list.pop_back();
			if(bucket.empty()) return 0;
			bucket.pop_back();
		}
		++cnt;
	}
	cnt += list.size() + bucket.size();
	return cnt;
}
int hubDistance(int N, int sub) {
	int mx = 0;
	for(int i=1; i<N; ++i) {
		from0[i] = getDistance(0, i);
		if(mx<from0[i]) {
			mx = from0[i];
			u = i;
		}
	}

	mx = 0;
	for(int i=0; i<N; ++i) {
		fromu[i] = getDistance(i, u);
		if(fromu[i]>mx) {
			mx = fromu[i];
			v = i;
		}
	}

	int R = 2e9;
	map<int, vector<int>>groups;


	for(int i=0; i<N; ++i) {
		int a_plus_b = from0[u];
		int b_plus_c = fromu[i];
		int c_plus_a = from0[i];

		int b = (b_plus_c - c_plus_a + a_plus_b) / 2;
		int d = fromu[v] - b;

		R = min(R, max(b, d));
		groups[b].push_back(i);

		c[i] = b_plus_c - b;
	}

	int big = -1;
	for(auto it : groups) {
		if(it.second.size()>N/2) {
			big = it.first;
		}
	}
	if(big==-1) return R;

	int mx_freq = Do_The_Majority_Thing(groups[big]);
	if(mx_freq>N/2) return -R;
	return R;
}

Compilation message

towns.cpp: In function 'bool EQUAL(int, int)':
towns.cpp:12:23: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   12 | bool EQUAL(int u, int v) {
      |                   ~~~~^
towns.cpp:10:8: note: shadowed declaration is here
   10 | int u, v;
      |        ^
towns.cpp:12:16: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   12 | bool EQUAL(int u, int v) {
      |            ~~~~^
towns.cpp:10:5: note: shadowed declaration is here
   10 | int u, v;
      |     ^
towns.cpp: In function 'int Do_The_Majority_Thing(std::vector<int>)':
towns.cpp:18:38: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   18 | int Do_The_Majority_Thing(vector<int>v) {
      |                           ~~~~~~~~~~~^
towns.cpp:10:8: note: shadowed declaration is here
   10 | int u, v;
      |        ^
towns.cpp:21:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   21 |  int n = v.size();
      |          ~~~~~~^~
towns.cpp:51:35: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |  cnt += list.size() + bucket.size();
      |                                   ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:93:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |   if(it.second.size()>N/2) {
      |      ~~~~~~~~~~~~~~~~^~~~
towns.cpp:54:28: warning: unused parameter 'sub' [-Wunused-parameter]
   54 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 12 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 340 KB Output is correct
5 Correct 13 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 360 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 14 ms 348 KB Output is correct
4 Correct 14 ms 340 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -