Submission #1173277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173277		nuutsnoynton	Drzava (COCI15_drzava)	C++20	72 / 160	274 ms	9540 KiB

drzava

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, pair < ll, ll > >;
const ll N = 5e4 + 2;
ll x[N], y[N], c[N];
ll ataman[N], k, n;
vector < pll > X, Y;
vector < pll > SUM_X, SUM_Y;
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 ( r = 1; r < X.size(); r ++) {
		i = X[r - 1].second.second;
		j = X[r].second.second;
		S =(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j] ) * (y[i] - y[j]);
		if ( S <= K) {
			Unite(i, j);
		}
	}
	for ( r = 1; r < Y.size(); r ++) {
		i = Y[r - 1].second.second;
		j = Y[r].second.second;
		S =(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j] ) * (y[i] - y[j]);
		if ( S <= K) {
			Unite(i, j);
		}
	}
	for ( r = 1; r < SUM_X.size(); r ++) {
		i = SUM_X[r - 1].second.second;
		j = SUM_X[r].second.second;
		S =(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j] ) * (y[i] - y[j]);
		if ( S <= K) {
			Unite(i, j);
		}
	}
	for ( r = 1; r < SUM_Y.size(); r ++) {
		i = SUM_Y[r - 1].second.second;
		j = SUM_Y[r].second.second;
		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;
		X.push_back(make_pair(x[i], make_pair(y[i], i)));
		Y.push_back(make_pair(y[i], make_pair(x[i], i)));
		SUM_X.push_back(make_pair(x[i] + y[i], make_pair(x[i], i)));
		SUM_Y.push_back(make_pair(x[i] + y[i], make_pair(y[i], i)));
	}
	sort(X.begin(), X.end());
	sort(SUM_X.begin(), SUM_X.end());
	sort(SUM_Y.begin(), SUM_Y.end());
	sort(Y.begin(), Y.end());
	
	double lo , mid , hi;
	
	lo = 0;
	hi = 4e9;
//	cout << Can(2) << endl;
	while ( hi - lo > 0.0000001) {
		mid = (lo+ hi)/2;
		if (!Can(mid)) lo = mid + 0.00000001;
		else hi = mid;
	}
	printf("%.3lf", lo);
}

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