#include<bits/stdc++.h>
#define ld long double
using namespace std;
const int N = 5e4 + 5, M = 31;
int n, k, x[N], y[N], z[N], a[N], p[N];
bool dp[N][M];
inline bool cmp(int xx, int yy){
return x[xx] < x[yy] || (x[xx] == x[yy] && y[xx] < y[yy]);
}
inline long long dist(int i, int j){
return 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]);
}
int dsu_get(int v){
return p[v] == v ? v : p[v] = dsu_get(p[v]);
}
inline void dsu_unite(int x, int y){
x = dsu_get(x);
y = dsu_get(y);
if(x == y){
return;
}
if(rand() & 1){
swap(x, y);
}
p[y] = x;
bool ndp[M];
for(int i = 0; i < k; i++){
ndp[i] = (dp[x][i] | dp[y][i]);
}
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
ndp[(i + j) % k] |= (dp[x][i] & dp[y][j]);
}
}
for(int i = 0; i < k; i++){
dp[x][i] |= ndp[i];
}
}
inline bool check(long long val){
for(int i = 1; i <= n; i++){
p[a[i]] = a[i];
memset(dp[a[i]], 0, sizeof(dp[a[i]]));
dp[a[i]][z[a[i]]] = true;
}
set < pair < int, int > > q;
q.insert(make_pair(y[a[1]], a[1]));
int bound = (int)ceil(sqrt(val)) + 1;
for(int i = 2, j = 1; i <= n; i++){
while(x[a[i]] - x[a[j]] > bound){
q.erase(make_pair(y[a[j]], a[j]));
j += 1;
}
for(auto it = q.lower_bound(make_pair(y[a[i]] - bound, -1)); it != q.end(); it++){
if(abs(y[a[i]] - it->first) > bound){
break;
}
if(dist(a[i], it->second) <= val){
dsu_unite(a[i], it->second);
}
if(dp[dsu_get(a[i])][0] == true){
return true;
}
}
if(dp[dsu_get(a[i])][0]){
return true;
}
q.insert(make_pair(y[a[i]], a[i]));
}
return false;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
srand(time(nullptr));
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i] >> z[i];
z[i] %= k;
a[i] = i;
}
sort(a + 1, a + n + 1, cmp);
long long l = 0, r = 2e18;
while(r - l > 1){
long long mid = (r + l) >> 1;
if(check(mid)){
r = mid;
}
else{
l = mid;
}
}
if(check(l)){
cout << fixed << setprecision(3) << sqrtl(l);
}
else{
cout << fixed << setprecision(3) << sqrtl(r);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
18 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
44 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
130 ms |
2940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
153 ms |
2808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
123 ms |
2844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
120 ms |
2888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
252 ms |
2884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
300 KB |
Output is correct |
2 |
Correct |
89 ms |
2908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
112 ms |
2816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
93 ms |
2816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
88 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
300 KB |
Output is correct |
2 |
Correct |
95 ms |
2864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
412 KB |
Output is correct |
2 |
Correct |
103 ms |
2876 KB |
Output is correct |