oj.uz

Submission #232578

# Submission time Handle Problem Language Result Execution time Memory
232578 2020-05-17T12:26:10 Z alishahali1382 Drzava (COCI15_drzava) C++14
160 / 160
 227 ms 1404 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define get(x, y) (((x)>>(y))&1)

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=50010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
piii A[MAXN];
int par[MAXN], dp[MAXN];
set<pii> st;

int getpar(int x){
	if (par[x]==x) return x;
	return par[x]=getpar(par[x]);
}
bool join(int x, int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return 0;
	par[y]=x;
	//debug2(x, y)
	//cerr<<dp[x]<<' '<<dp[y]<<" : ";
	for (int i=1; i<k; i++) if (get(dp[x], i) && get(dp[y], k-i)) return 1;
	int tmp=dp[x];
	for (int i=1; i<k; i++) if (get(dp[y], i)){
		dp[x]|=((((1<<(k-i))-1)&tmp)<<i);
		dp[x]|=(tmp>>(k-i));
	}
	//cerr<<dp[x]<<endl;
	return 0;
}

ld dist(int i, int j){
	ld dx=A[i].first.first-A[j].first.first, dy=A[i].first.second-A[j].first.second;
	return sqrt(dx*dx+dy*dy);
}

bool check(ld D){
	if (D<1) return 0;
	int DD=D+1;
	iota(par, par+MAXN, 0);
	for (int i=1; i<=n; i++) dp[i]=(1|(1<<A[i].second));
	st.clear();
	int j=1;
	for (int i=1; i<=n; i++){
		while (A[i].first.first-A[j].first.first>DD){
			st.erase({A[j].first.second, j});
			j++;
		}
		//debug2(i, j)
		int y=A[i].first.second;
		auto it=st.lower_bound({y-DD, 0});
		while (1){
			if (it==st.end() || (it->first)>y+DD) break ;
			if (dist(i, (it->second))<=D){
				if (join(i, (it->second))) return 1;
			}
			it=st.upper_bound(*it);
		}
		st.insert({y, i});
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k;
	for (int i=1; i<=n; i++) cin>>A[i].first.first>>A[i].first.second>>A[i].second, A[i].second%=k;
	sort(A+1, A+n+1);
	/*
	debug(check(20000))
	return 0;
	*/
	ld dwn=0, up=2e8;
	for (int i=0; i<50; i++){
		ld mid=(dwn+up)/2;
		if (check(mid)) up=mid;
		else dwn=mid;
	}
	cout<<setprecision(3)<<fixed<<up<<'\n';
	
	return 0;
}
/*
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10


5 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 9 ms 512 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 640 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 512 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 51 ms 896 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 151 ms 1280 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 227 ms 1336 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 113 ms 1280 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 151 ms 1376 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 109 ms 1280 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 101 ms 1280 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 114 ms 1368 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 58 ms 1280 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 127 ms 1280 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 109 ms 1280 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 123 ms 1404 KB Output is correct