Submission #264748

#	Time	Username	Problem	Language	Result	Execution time	Memory
264748		patrikpavic2	Towns (IOI15_towns)	C++17	0 / 100	8 ms	2688 KiB

towns

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  towns
* score: 0.0
* date:  2019-06-23 11:08:12.761811
*/
#include "towns.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

const int N = 505;
const int INF = 0x3f3f3f3f;

typedef pair < int, int > pii;
typedef vector < pii > vp;
typedef vector < int > vi;

int dis[N][N], un[N], sk, n;
vp v[N];

void spajaj(){
	int piv = 0, edg = 0;
	for(;!un[piv];piv++);
	vi klik;
	for(int i = 0;i < n;i++){
		if(i == piv || !un[i]) continue;
		int mx = -INF, mi = INF;
		for(int j = 0;j < n;j++){

			if(j == i) continue;
			if(j == piv || !un[j]) continue;
			mi = min(mi, dis[i][j] - dis[piv][j]);	
			mx = max(mi, dis[i][j] - dis[piv][j]);	
		}
		//printf("mi %d mx %d i %d piv %d\n", mi, mx, i, piv);
		if(mi != mx) continue;
		if(dis[piv][n] && dis[piv][n]  != (dis[i][piv] - mi) / 2) continue;
		dis[piv][n] = (dis[i][piv] - mi) / 2;
		dis[i][n]   = (dis[i][piv] + mi) / 2;
		dis[n][i] = dis[i][n];
		dis[n][piv] = dis[piv][n];
		v[n].PB({i, dis[i][n]});
		v[i].PB({n, dis[i][n]});
		//printf("%d spojena na %d s tezinom %d\n", i, n, dis[i][n]);
		sk--;// un[i] = 0;
		klik.PB(i);
	}
	for(int x : klik) un[x] = 0;
	v[n].PB({piv, dis[piv][n]});
	v[piv].PB({n, dis[piv][n]});
	//printf("%d spojena na %d s tezinom %d\n", piv, n, dis[piv][n]);

	un[n] = 1; un[piv] = 0;
	for(int i = 0;i < n;i++){
		if(!un[i]) continue;
		dis[n][i] = dis[piv][i] - dis[piv][n];
		//printf("dis %d %d je %d\n", n, i, dis[n][i]);
		dis[i][n] = dis[n][i];
	}
	n++; 
	//printf("gotov\n");
}

int R(int x,int lst){
	int ret = 0;
	for(pii y : v[x]){
		if(y.X == lst) continue;
		ret =  max(R(y.X, x) + y.Y, ret);
	}
	return ret;
}

int C(int x,int lst){
	if(v[x].size() == 1) return 1;
	int ret = 0;
	for(pii y : v[x]){
		if(y.X == lst) continue;
		ret += C(y.X, x);
	}
	return ret;
}

int hubDistance(int nn, int sub) {
	for(int i = 0;i < N;i++) v[i].clear(), un[i] = 0;
	memset(dis, 0, sizeof(dis));
	n = nn;
	for(int i = 0;i < n;i++){
		dis[i][i] = 0; un[i] = 1;
		for(int j = i + 1;j < n;j++){
			dis[i][j] = getDistance(i, j);
			dis[j][i] = dis[i][j];
		}
	}
	sk = n;
	int T = 0;
	while(sk > 1){
		spajaj();
	}
	int ans = INF, ima = 0;
	for(int i = nn;i < n;i++)
		ans = min(ans, R(i, i));
	for(int i = nn;i < n;i++){
		if(R(i, i) != ans) continue;
		int pos = 1;
		for(pii y : v[i]){
			if(C(y.X, i) > 2 * n) pos = 0;
		}		
		ima += pos;
	}
	if(sub < 3) return ans;
	if(ima) return ans;
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'void spajaj()':
towns.cpp:32:15: warning: unused variable 'edg' [-Wunused-variable]
   32 |  int piv = 0, edg = 0;
      |               ^~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:105:6: warning: unused variable 'T' [-Wunused-variable]
  105 |  int T = 0;
      |      ^

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