Submission #286453

#	Time	Username	Problem	Language	Result	Execution time	Memory
286453		abyyskit	Towns (IOI15_towns)	C++14	0 / 100	1080 ms	504 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
vector<vector<int>> D;

//int getDistance(int a, int b){
//	return D[a][b];
//}

int hubDistance(int N, int sub) {
	bool FLAG = false;
	//int R = getDistance(0,1);
	vector<vector<int>> d(N, vector<int> (N));
	FOR(i, 0, N){
		FOR(j, i + 1, N){
			d[i][j] = getDistance(i, j);
			d[j][i] = d[i][j];
		}
	}
	int ans = INT_MAX;
	FOR(i, 0, N){
		FOR(j, i + 1, N){
			FOR(k, j + 1, N){
				int big = 0;
				int tmp = d[i][j] + d[j][k] + d[k][i];
				int a = tmp - 2*d[j][k];
				int b = tmp - 2*d[i][k];
				int c = tmp - 2*d[i][j];
				a /= 2;
				b /= 2;
				c /= 2;
				vector<int> side = {a, b, c};
				vector<int> ind = {i, j, k};
				vector<int> count = {1, 1, 1};
				FOR(h, 0, N){
					int as = d[h][i] - a;
					int bs = d[h][j] - b;
					int cs = d[h][k] - c;
					if (as == bs){
						big = max(big, as);
					}
					else if (as == cs){
						big = max(big, as);
					}
					else{
						big = max(big, bs);
					}
					bool flag = true;
					if (!FLAG){
					FOR(ii, 0, side.size()){
						if (side[ii] - d[ind[ii]][j] < 0){
							flag = false;
							count[ii]++;
							break;
						}
					}
					if (flag){
						side.pb(as);
						ind.pb(h);
						count.pb(1);
					}
					}
				}
				if (!FLAG){
				bool flag = true;
				FOR(h, 0, count.size()){
					if (count[i] > N/2){
						flag = false;
						break;
					}
				}
				if (flag){
					FLAG = true;
				}
				}
				ans = min(ans, big);
			}
		}
	}
	//cout << ans << "\n";
	if (FLAG){
		return ans;
	}
	return -ans;
}

/*int main(){
	int n, s;
	ifstream fin("towns.in");
	fin >> n >> s;
	fin >> n;
	D.resize(n, vector<int>(n));
	FOR(i, 0, n){
		FOR(j, 0, n){
			fin >> D[i][j];
		}
	}
	hubDistance(n, s);
}*/

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   52 |      FOR(ii, 0, side.size()){
      |          ~~~~~~~~~~~~~~~~~~            
towns.cpp:52:6: note: in expansion of macro 'FOR'
   52 |      FOR(ii, 0, side.size()){
      |      ^~~
towns.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   68 |     FOR(h, 0, count.size()){
      |         ~~~~~~~~~~~~~~~~~~             
towns.cpp:68:5: note: in expansion of macro 'FOR'
   68 |     FOR(h, 0, count.size()){
      |     ^~~
towns.cpp:12:28: warning: unused parameter 'sub' [-Wunused-parameter]
   12 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39