Submission #1173240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173240		nuutsnoynton	Drzava (COCI15_drzava)	C++20	24 / 160	1096 ms	2016 KiB

drzava

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 5e4 + 2;
ll x[N], y[N], c[N];
ll ataman[N], k, n;

ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	if ( x > y) swap(x, y);
	ataman[y] = x;
	return ;
}

bool Can(double R) {
	double S, K = R * R;
	ll i, j, r, cur;
	for (i = 1; i <= n; i ++) ataman[i] = i;
	for (i = 1; i <= n; i ++) {
		for (j = i + 1; j <= n; j ++) {
			S =(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j] ) * (y[i] - y[j]);
			if ( S <= K) {
				Unite(i, j);
			}
		}
	}
	vector < ll > v[n + 2];
	for (i = 1; i <= n; i ++) {
//		cout << Get(i) << " ";
		v[Get(i)].push_back(i);
	}
//	cout << "\n";
	for (i = 1; i <= n; i ++) {
		ll A[3][32] = {0};
		A[0][0] = 1;
		cur = 0;
		for (j = 0; j < v[i].size();  j ++) {
		//	cout << c[v[i][j]] << " ";
			for ( r = 0; r < k; r ++) A[1 - cur][r] = 0;
			for ( r = 0; r < k; r ++) {
				A[1 - cur][(r + c[v[i][j]]) % k]  += A[cur][r];
				A[1 - cur][r]  += A[cur][r];
			}
			cur = 1 - cur;
		}
		if ( A[cur][0] > 1) return true;
	}
	return false;
	
}

int main() {
	ll i;

	cin >> n >> k;
	
	for (i = 1; i <= n; i ++) {
		cin >> x[i] >> y[i] >> c[i];
		c[i] %= k;
	}
	
	double lo , mid , hi;
	
	lo = 0;
	hi = 1e9;
//	cout << Can(2) << endl;
	while ( hi - lo > 0.00001) {
		mid = (lo+ hi)/2;
		if (!Can(mid)) lo = mid + 0.00001;
		else hi = mid;
	}
	printf("%.3lf", lo);
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 8 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 8 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8
• Subtask 14: 0 / 8
• Subtask 15: 0 / 8
• Subtask 16: 0 / 8
• Subtask 17: 0 / 8
• Subtask 18: 0 / 8
• Subtask 19: 0 / 8
• Subtask 20: 0 / 8