oj.uz

Submission #96584

# Submission time Handle Problem Language Result Execution time Memory
96584 2019-02-10T11:03:52 Z groeneprof Towns (IOI15_towns) C++14
0 / 100
 65 ms 8404 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<int> > adj(120, vector<int> (120, -1));
int gD(int i, int j){
	if(i==j) return 0;
	if(adj[i][j]==-1){
		return adj[i][j] = adj[j][i] = getDistance(i, j);
	}
	return adj[i][j];
}
int hubDistance(int N, int sub) {
	sub = sub*sub;
	//cout<<"haaaahaaaaaaaHHZHEAHJAHAAAAAAA"<<endl;
	int u=0, maxv = 0;
	for(int i =1; i<N; i++){
		if(gD(i, 0)>maxv){
			u = i;
			maxv = gD(i, 0);
		}
	}
	maxv = 0;
	int v = 0;
	for(int i = 0; i<N; i++) if(i!=u){
		if(gD(u, i)>maxv){
			v = i;
			maxv = gD(u, i);
		}		
	}
	//cout<<u<<" "<<v<<endl;
	vector<int> diam(2e6+5, 0);
	//int minimax = 1000000;
	for(int i = 0; i<N; i++){
		int x,y,z;
		x = gD(u, v);
		y = gD(u, i);
		z = gD(v, i);
		//cout<<i<<": "<<(x+y-z)/2<<endl;
		diam[(x+y-z)/2]++;
	}
	int R = 10000000;
	int Ri = 0;
	/*for(int i = 0; i<30; i++){
		cout<<diam[i]<<" ";
	}
	*/
	//cout<<endl;
	for(int i = 0; i<=gD(u,v); i++){
		if(diam[i]>0&&R>max(i, gD(u,v)-i)){
			R =  max(i , gD(u,v)-i);
			Ri = i;
			//cout<<"i: "<<i<<" R: "<<R<<endl;
		}
	}
	/*int boven = 0, onder = 0;
	for(int i = 0; i<(int)diam.size(); i++){
		if(i<Ri) onder++;
		if(i>Ri) boven++;
	}
	if(boven>N/2 || onder > N/2 || N-boven-onder>N/2) R = -R;*/
	return abs(R);
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:43:6: warning: variable 'Ri' set but not used [-Wunused-but-set-variable]
  int Ri = 0;
      ^~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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