oj.uz

Submission #20195

# Submission time Handle Problem Language Result Execution time Memory
20195 2016-03-06T10:50:12 Z suhgyuho_william Towns (IOI15_towns) C++
25 / 100
 23 ms 4 KB 
#include "towns.h"
#include <algorithm>
#include <stdio.h>

using namespace std;

int N,R;
int v,big;
int a[150][150];
int x[150],towns[150],tmp[150];
int cnt[150],far[150];
int left[150],right[150];

void getR(){
	int i,j;
	int rear,t;

	for(i=1; i<N; i++) a[0][i] = a[i][0] = getDistance(0,i);
	big = 0;
	for(i=1; i<N; i++){
		if(big < a[0][i]){
			big = a[0][i];
			v = i;
		}
	}
	for(i=1; i<N; i++){
		if(i == v) continue;
		a[v][i] = a[i][v] = getDistance(i,v);
	}
	rear = 0;
	for(i=1; i<N; i++){
		if(i == v) continue;
		x[i] = a[0][i]+a[v][i]-big;
		x[i] /= 2;
		rear++;
		towns[rear] = a[0][i]-x[i];
	}
	sort(towns+1,towns+rear+1);
	t = 0;
	for(i=1; i<=rear; i++){
		if(towns[i] == towns[i-1]) continue;
		t++;
		tmp[t] = towns[i];
	}
	rear = t;
	for(i=1; i<=rear; i++) towns[i] = tmp[i];
	for(i=1; i<=rear; i++) cnt[i] = 0;
	R = 1000000;
    for(i=1; i<=rear; i++){
		far[i] = 0;
		for(j=1; j<N; j++){
			if(j == v) continue;
			if(a[0][j]-x[j] == towns[i]){
				cnt[i]++;
				far[i] = max(far[i],x[j]);
			}
		}
    }
    left[1] = towns[1];
	for(i=2; i<=rear; i++){
		left[i] = max(left[i-1],far[i-1])+(towns[i]-towns[i-1]);
	}
	right[rear] = big-towns[rear];
	for(i=rear-1; i>=1; i--){
		right[i] = max(right[i+1],far[i+1])+(towns[i+1]-towns[i]);
	}
	for(i=1; i<=rear; i++){
		R = min(R,max(far[i],max(left[i],right[i])));
	}
}

int hubDistance(int n, int sub) {
	N = n;
	getR();

	return R;
}

Compilation message

towns.cpp:72: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 19 ms 0 KB Output is correct
2 Correct 17 ms 1 KB Output is correct
3 Correct 2 ms 1 KB Output is correct
4 Correct 21 ms 1 KB Output is correct
5 Correct 22 ms 2 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3 KB Output is correct
2 Correct 17 ms 3 KB Output is correct
3 Correct 23 ms 3 KB Output is correct
4 Correct 21 ms 4 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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