oj.uz

Submission #30678

# Submission time Handle Problem Language Result Execution time Memory
30678 2017-07-26T05:40:58 Z noobprogrammer Park (BOI16_park) C++14
100 / 100
 1299 ms 3248 KB 
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define ii pair<ll,ll>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>
inline ll sqr(ll x) { return (ll)x*(ll)x ;} 

// define 0 = up , 1 = dw , 2 = lft , 3 = right 
int n , m , par[2010] , qr[100005] ;
ll w , h ;
ll sz[100005] , lim[10][10] ;
ll rd[2005] ;
ii coor[2005] ;

int find_root(int x){
	if(par[x] == x) return x ;
	return par[x] = find_root(par[x]) ;
}

ll dist(ii a , ii b){
	return sqr(a.fi - b.fi) + sqr(a.se - b.se) ;
}

bool chk(int x , int y , ll k ){
	// printf("%d %d %lld :: \n" , x , y , k ) ;
	for(int i=0;i<n+4;i++) par[i] = i ; 
	for(int i=0;i<n;i++){
		int pr = find_root(i) ;
		if(coor[i].se - rd[i] - 2*k < 0) if(find_root(n) != pr) par[find_root(n)]  = pr ;
		if(coor[i].se + rd[i] + 2*k > h) if(find_root(n + 1) != pr) par[find_root(n+1)] = pr ;  
		if(coor[i].fi - rd[i] - 2*k < 0) if(find_root(n + 2) != pr) par[find_root(n+2)] = pr ;  
		if(coor[i].fi + rd[i] + 2*k > w) if(find_root(n + 3) != pr) par[find_root(n+3)] = pr ;  
		for(int j=i+1;j<n;j++){
			if(dist(coor[i] , coor[j]) < sqr(rd[i] + rd[j] + 2*k) ) {
				if(find_root(j) != pr) par[find_root(j)] = pr ; 
				// printf("1 %d %d %lld %lld\n" , i , j , dist(coor[i] , coor[j]) , sqr(rd[i] + rd[j] + 2*k)) ;
			}
		}
	}
	int p0 = find_root(n) , p1 = find_root(n+1) , p2 = find_root(n+2) , p3 = find_root(n+3) ;
	// printf("%d %d %d %d : %d %d %lld\n", p0 , p1 , p2 , p3 , x  ,y ,k );
	if(x == y) return 1 ;
	if(y == 1){
		if(p0 == p2) return 0 ;
		if(x == 3 && ( p0 == p1 || p2 == p3 ) ) return 0 ;
		if(x == 2 && (p0 == p1) ) return 0 ;
		if(x == 4 && (p2 == p3) ) return 0; 
	}
	else if(y == 2){
		if(p0 == p3) return 0 ;
		if(x == 4 && ( p0 == p1 || p2 == p3 ) ) return 0 ;
		if(x == 1 && (p0 == p1) ) return 0 ;
		if(x == 3 && (p2 == p3) ) return 0; 
	}	
	else if(y == 3){
		if(p1 == p3) return 0 ;
		if(x == 1 && ( p0 == p1 || p2 == p3 ) ) return 0 ;
		if(x == 4 && (p0 == p1) ) return 0 ;
		if(x == 2 && (p2 == p3) ) return 0; 
	}
	else{
		if(p1 == p2) return 0 ;
		if(x == 2 && ( p0 == p1 || p2 == p3 ) ) return 0 ;
		if(x == 3 && ( p0 == p1 ) ) return 0 ;
		if(x == 1 && ( p2 == p3 ) ) return 0; 
	}
	if(x == 1 && (p0 == p2)) return 0 ;
	if(x == 2 && (p0 == p3)) return 0 ;
	if(x == 3 && (p1 == p3)) return 0 ;
	if(x == 4 && (p1 == p2)) return 0 ;
	return 1 ;
}

int main(){
	// freopen("in.txt" , "r" ,stdin) ;
	// freopen("out.txt" , "w" , stdout ) ;
	scanf("%d%d%lld%lld" , &n,&m,&w,&h) ;
	int a , b , c ; 
	for(int i=0;i<n;i++) {
		scanf("%d%d%d",&a,&b,&c) ;
		coor[i] = {a,b} ;
		rd[i] = c ; 
	}
	ll mx = 0 ;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b) ;
		qr[i] = b ; 
		sz[i] = a ; 
		mx = max(mx , (ll)a) ; 
	}
	ll f , l , mid ;
	for(int i=1;i<=4;i++){
		lim[i][i] = mx ; 
		for(int j=i+1;j<=4;j++){
			f = 0 , l = mx ;
			while(f <= l){
				mid = (f+l)/2 ;
				if(chk(i,j,mid)){
					lim[i][j] = mid ;
					f = mid + 1 ;
				}
				else l = mid - 1 ;
			}
			lim[j][i] = lim[i][j] ;
		}
	}
	for(int i=0;i<m;i++){
		b = qr[i] ; 
		for(int j=1;j<=4;j++){
			if(lim[b][j] >= sz[i]) printf("%d",j) ;
		}
		printf("\n");
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:80:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld%lld" , &n,&m,&w,&h) ;
                                      ^
park.cpp:83:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c) ;
                            ^
park.cpp:89:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b) ;
                       ^

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 3248 KB Output is correct
2 Correct 713 ms 3248 KB Output is correct
3 Correct 669 ms 3248 KB Output is correct
4 Correct 629 ms 3248 KB Output is correct
5 Correct 656 ms 3248 KB Output is correct
6 Correct 646 ms 3248 KB Output is correct
7 Correct 1299 ms 3248 KB Output is correct
8 Correct 556 ms 3248 KB Output is correct
9 Correct 0 ms 3248 KB Output is correct
10 Correct 0 ms 3248 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3248 KB Output is correct
2 Correct 59 ms 3248 KB Output is correct
3 Correct 59 ms 3248 KB Output is correct
4 Correct 66 ms 3248 KB Output is correct
5 Correct 66 ms 3248 KB Output is correct
6 Correct 73 ms 3248 KB Output is correct
7 Correct 46 ms 3248 KB Output is correct
8 Correct 49 ms 3248 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 3248 KB Output is correct
2 Correct 713 ms 3248 KB Output is correct
3 Correct 669 ms 3248 KB Output is correct
4 Correct 629 ms 3248 KB Output is correct
5 Correct 656 ms 3248 KB Output is correct
6 Correct 646 ms 3248 KB Output is correct
7 Correct 1299 ms 3248 KB Output is correct
8 Correct 556 ms 3248 KB Output is correct
9 Correct 0 ms 3248 KB Output is correct
10 Correct 0 ms 3248 KB Output is correct
11 Correct 53 ms 3248 KB Output is correct
12 Correct 59 ms 3248 KB Output is correct
13 Correct 59 ms 3248 KB Output is correct
14 Correct 66 ms 3248 KB Output is correct
15 Correct 66 ms 3248 KB Output is correct
16 Correct 73 ms 3248 KB Output is correct
17 Correct 46 ms 3248 KB Output is correct
18 Correct 49 ms 3248 KB Output is correct
19 Correct 646 ms 3248 KB Output is correct
20 Correct 686 ms 3248 KB Output is correct
21 Correct 673 ms 3248 KB Output is correct
22 Correct 583 ms 3248 KB Output is correct
23 Correct 646 ms 3248 KB Output is correct
24 Correct 1269 ms 3248 KB Output is correct