oj.uz

Submission #20196

# Submission time Handle Problem Language Result Execution time Memory
20196 2016-03-06T12:43:15 Z suhgyuho_william Towns (IOI15_towns) C++
36 / 100
 40 ms 2 KB 
#include "towns.h"
#include <algorithm>
#include <stdio.h>

using namespace std;

int N,R,f;
int v,big;
int a[150][150];
int x[150],towns[150],tmp[150];
int cnt[150],far[150];
int left[150],right[150];
int leftcnt[150],rightcnt[150];
bool hub[150],flag;
int num[150],color[150],colorcnt[150];

void checking(int hubnum){
	int i,j;
	int rear;

	rear = 0;
	for(i=1; i<N; i++){
        if(i == v) continue;
		if(towns[hubnum] == a[0][i]-x[i]){
			rear++;
			num[rear] = i;
		}
	}
	for(i=1; i<=rear; i++) colorcnt[i] = 0;
	for(i=1; i<=rear; i++){
        for(j=1; j<i; j++){
			if(getDistance(num[i],num[j]) != x[num[i]]+x[num[j]]) break;
        }
        if(j == i){
			color[i] = i;
			colorcnt[i]++;
        }else{
			color[i] = color[j];
			colorcnt[color[i]]++;
        }
	}
	flag = true;
	for(i=1; i<=rear; i++){
		if(colorcnt[i] > f) flag = false;
	}
}

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

	f = N/2;
	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];
    leftcnt[1] = 1;
	for(i=2; i<=rear; i++){
		left[i] = max(left[i-1],far[i-1])+(towns[i]-towns[i-1]);
		leftcnt[i] = leftcnt[i-1]+cnt[i-1];
	}
	right[rear] = big-towns[rear];
	rightcnt[rear] = 1;
	for(i=rear-1; i>=1; i--){
		right[i] = max(right[i+1],far[i+1])+(towns[i+1]-towns[i]);
		rightcnt[i] = rightcnt[i+1]+cnt[i+1];
	}
	for(i=1; i<=rear; i++){
		R = min(R,max(far[i],max(left[i],right[i])));
	}
	for(i=1; i<=rear; i++){
		if(R == max(far[i],max(left[i],right[i]))) hub[i] = true;
		else hub[i] = false;
	}
	flag = false;
	for(i=1; i<=rear; i++){
		if(!hub[i]) continue;
		if(cnt[i] <= f && leftcnt[i] <= f && rightcnt[i] <= f){
			flag = true;
		}
	}
	if(flag) return;
	for(i=1; i<=rear; i++){
		if(!hub[i]) continue;
        if(leftcnt[i] <= f && rightcnt[i] <= f && cnt[i] > f){
			checking(i);
        }
	}
	if(!flag) R = -R;
}

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

	return R;
}

Compilation message

towns.cpp:130: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 20 ms 0 KB Output is correct
2 Correct 16 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 20 ms 1 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1 KB Output is correct
2 Correct 20 ms 1 KB Output is correct
3 Correct 1 ms 2 KB Output is correct
4 Correct 40 ms 2 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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