oj.uz

Submission #96586

# Submission time Handle Problem Language Result Execution time Memory
96586 2019-02-10T11:12:26 Z groeneprof Towns (IOI15_towns) C++14
35 / 100
 132 ms 8312 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) {
	adj.assign(120, vector<int> (120, -1));
	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+=diam[i];
		if(i>Ri) boven+=diam[i];
	}
	//cout<<boven<<" "<<onder<<endl;
	if(boven>N/2 || onder > N/2 || N-boven-onder>N/2) R = -R;
	return R;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8276 KB Output is correct
2 Correct 69 ms 8260 KB Output is correct
3 Correct 10 ms 8184 KB Output is correct
4 Correct 77 ms 8300 KB Output is correct
5 Correct 103 ms 8308 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8312 KB Output is correct
2 Correct 72 ms 8304 KB Output is correct
3 Correct 79 ms 8312 KB Output is correct
4 Correct 75 ms 8300 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8300 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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