oj.uz

Submission #64743

# Submission time Handle Problem Language Result Execution time Memory
64743 2018-08-05T13:51:31 Z FLDutchman Towns (IOI15_towns) C++14
13 / 100
 27 ms 780 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

const int mod = 1e9+7;
int D;



INT hubDistance(INT N, INT sub) {
	vvi dist(N);
	FOR(i, 0, N) FOR(j, 0, N){
		if(j < i) dist[i].pb(dist[j][i]);
		else if (j == i) dist[i].pb(0);
		else dist[i].pb(getDistance(i, j));
	}

	ii far = {-1, -1};
	FOR(i, 1, N) far = max(far, {dist[0][i], i});
	int I = far.snd;
	far = {-1, -1};
	FOR(i, 0, N) far = max(far, {dist[I][i], i});
	int J = far.snd;
	D = far.fst;
	map<int, vi> pts;
	int R = 1e9;;
	FOR(i, 0, N){
		int d = (dist[I][i] + dist[J][i] - D)/2;
		pts[dist[I][i]-d].pb(i);
		R = min(R, max(dist[I][i]-d, dist[J][i] - d));
	}
	int e = 0;
	bool poss = false;
	if(!pts[R].empty()){
		// R is a possible balanced hub
		int largest = 0;
		vi counted(N, 0);
		for(int i : pts[R]){
			if(!counted[i]){
				int sz = 1;
				counted[i] = 1;
				int d = (dist[I][i] + dist[J][i] - D)/2;
				for(int j : pts[R]) if(!counted[j]){
					if(dist[I][j] - R + d == dist[I][i]) {
						sz++;
						counted[j] = 1;
					}
				}
				largest = max(sz, largest);
			}
		}
		if(largest <= N/2) poss = true;
	}
	if(!pts[D - R].empty()){
		R = D - R;
		// R is a possible balanced hub
		int largest = 0;
		vi counted(N, 0);
		for(int i : pts[R]){
			if(!counted[i]){
				int sz = 1;
				counted[i] = 1;
				int d = (dist[I][i] + dist[J][i] - D)/2;
				for(int j : pts[R]) if(!counted[j]){
					if(dist[I][j] - R + d == dist[I][i]) {
						sz++;
						counted[j] = 1;
					}
				}
				largest = max(sz, largest);
			}
		}
		R = D - R;
		if(largest <= N/2) poss = true;
	}

	if(!poss) return -R;

	int r2 = D - R;
	// amnt < R, = R, > R
	int l = 0, g = 0;
	int L = 0, G = 0;
	for(auto it : pts){
		if(pts[R].size() != 0){
			if(it.fst < R) l += it.snd.size();
			if(it.fst > R) g += it.snd.size();
		} 
		if(pts[r2].size() != 0){
			if(it.fst < r2) L += it.snd.size();
			if(it.fst > r2) G += it.snd.size();
		}
	}
	if(max(l, g) <= N/2) return R;
	if(max(L, G) <= N/2) return R;
	return -R;


}

/*
INT hubDistance(INT N, INT sub) {
	ii far = {-1, -1};
	FOR(i, 1, N) far = max({getDistance(0, i), i}, far);
	vi d1, d2;
	int I = far.snd;
	far = {-1, -1};
	FOR(i, 0, N) {
		if(i == I) d1.pb(0);
		else d1.pb(getDistance(I, i)), far = max(far, {d1.back(), i});
	}
	int J = far.snd;
	D = far.fst;
	FOR(i, 0, N){
		if(i == J) d2.pb(0);
		else d2.pb(getDistance(J, i));
	}
	int R = 1e9;
	map<int, int> cnt;
	FOR(i, 0, N){
		int d = (d1[i] + d2[i] - D)/2;
		cnt[d1[i]-d]++;
		R = min(R, max(d1[i]-d, d2[i]-d));
	}
	int r2 = D - R;
	// amnt < R, = R, > R
	int l = 0, e = 0, g = 0;
	int L = 0, E = 0, G = 0;
	for(auto it : cnt){
		if(cnt[R] != 0){
			if(it.fst < R) l += it.snd;
			if(it.fst == R) e += it.snd;
			if(it.fst > R) g += it.snd;
		} 
		if(cnt[r2] != 0){
			if(it.fst < r2) L += it.snd;
			if(it.fst == r2) E += it.snd;
			if(it.fst > r2) G += it.snd;
		}
	}
	if(max(l, max(e, g)) > N/2) R *= -1;
	if(max(L, max(E, G)) > N/2 and R >= 0) R *= -1;
	return R;
}
*/

Compilation message

towns.cpp: In function 'INT hubDistance(INT, INT)':
towns.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   else dist[i].pb(getDistance(i, j));
                                   ^
towns.cpp:29:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
towns.cpp:91:19: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  if(!poss) return -R;
                   ^~
towns.cpp:107:30: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  if(max(l, g) <= N/2) return R;
                              ^
towns.cpp:108:30: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  if(max(L, G) <= N/2) return R;
                              ^
towns.cpp:109:9: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return -R;
         ^~
towns.cpp:46:6: warning: unused variable 'e' [-Wunused-variable]
  int e = 0;
      ^
towns.cpp:24:28: warning: unused parameter 'sub' [-Wunused-parameter]
 INT hubDistance(INT N, INT sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 24 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 26 ms 616 KB Output is correct
5 Correct 27 ms 680 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 780 KB Output isn't correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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