oj.uz

Submission #140590

# Submission time Handle Problem Language Result Execution time Memory
140590 2019-08-03T16:10:49 Z SirCeness Towns (IOI15_towns) C++14
25 / 100
 23 ms 1016 KB 
#include "towns.h"
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x)  "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

int mat[150][150];

int n; 

int getdistance(int node1, int node2){
	if (mat[node1][node2] != -1) return mat[node1][node2];
	int ans = getDistance(node1, node2);
	mat[node1][node2] = ans;
	mat[node2][node1] = ans;
	return ans;
}


int getmaxdist(int node){
	int ans = node;
	int dist = 0;
	for (int i = 0; i < n; i++){
		if (i == node) continue;
		int res = getdistance(node, i);
		if (res > dist){
			dist = res;
			ans = i;
		}
	}
	return ans;
}



int hubDistance(int N, int sub) {
	
	for (int i = 0; i < 150; i++) for (int j = 0; j < 150; j++) mat[i][j] = -1;
	
	n = N;
	int node1 = getmaxdist(0);
	int node2 = getmaxdist(node1);
	int r = 100000000;
	int dist = getdistance(node1, node2);
	//cout << bas(node1) << bas(node2) << bas(dist) << endl;
	for (int i = 0; i < n; i++){
		if (i == node1 || i == node2) continue;
		int d1 = getdistance(i, node1);
		int d2 = getdistance(i, node2);
		int uzak = (d1+d2-dist)/2;
		int uzak1 = d1-uzak;
		int uzak2 = d2-uzak;
		//cout << bas(i) << bas(uzak1) << bas(uzak2) << bas(uzak) << endl;
		int rtmp = max(max(uzak, uzak1), uzak2);
		r = min(r, rtmp);
	}
	return r;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47: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 504 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 464 KB Output is correct
5 Correct 21 ms 496 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 376 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 504 KB Output isn't correct
2 Halted 0 ms 0 KB -