oj.uz

Submission #53679

# Submission time Handle Problem Language Result Execution time Memory
53679 2018-06-30T20:49:33 Z wilwxk Park (BOI16_park) C++17
0 / 100
 1569 ms 1088 KB 
#include <bits/stdc++.h>
using namespace std;

struct objeto {
	int x, y, r;
};

const int MAXN=4e3+5;
const int INF=2e9+4;
objeto v[MAXN];
int pai[MAXN];
int n, m, xx, yy;
int maior[6]; //flag=0=pisos//flag=1=lados

int encon(int z) {
	if(pai[z]==z) return z;
	return pai[z]=encon(pai[z]);
}
void une(int a, int b) {
	a=encon(a); b=encon(b);
	if(a==b) return;
	if(rand()&1) swap(a, b);
	pai[a]=b;
}

bool toca(int a, int b) {
	long long aa=v[a].x-v[b].x; aa*=aa;
	long long bb=v[a].y-v[b].y; bb*=bb;
	long long cc=v[a].r+v[b].r; cc*=cc;
	aa+=bb; if(aa<cc) return 1;
	return 0;
}

bool testa(int k, int flag) { //flag=0=pisos//flag=1=lados
	for(int i=0; i<m; i++) v[i].r+=k;
	for(int i=0; i<m+5; i++) pai[i]=i;
	//m=cima//m+1=baixo//m+2=esquerda//m+3=direita
	printf("testa %d\n", k);
	for(int i=0; i<m; i++) {
		if(v[i].x-v[i].r<k) une(i, m+2); if(v[i].x+v[i].r>xx-k) une(i, m+3);
		if(v[i].y-v[i].r<k) une(i, m); if(v[i].y+v[i].r>yy-k) une(i, m+1);
		for(int j=i+1; j<m; j++) {
			if(toca(i, j)) une(i, j);
		}
	}
	
	bool a[6];
	a[0]=encon(m)!=encon(m+1);
	a[1]=encon(m+2)!=encon(m+3);
	a[2]=encon(m)!=encon(m+2);
	a[3]=encon(m)!=encon(m+3);
	a[4]=encon(m+1)!=encon(m+2);
	a[5]=encon(m+1)!=encon(m+3);
	
	for(int i=0; i<m; i++) v[i].r-=k;
	for(int i=0; i<m+5; i++) pai[i]=i;
	
	return a[flag];
}


int main() {
		
	scanf("%d %d", &m, &n);
	scanf("%d %d", &xx, &yy);
	for(int i=0; i<m; i++) {
		int a, b, c; scanf("%d %d %d", &a, &b, &c);
		v[i].x=a; v[i].y=b; v[i].r=c;
	}
	
	for(int kk=0; kk<6; kk++) for(int i=INF; i>0; i/=2) while(testa(maior[kk]+i, 0)) maior[kk]+=i;
	
	for(int i=0; i<n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		for(int j=0; j<6; j++) printf("1");
		
		
	}
	
}

Compilation message

park.cpp: In function 'bool testa(int, int)':
park.cpp:40:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(v[i].x-v[i].r<k) une(i, m+2); if(v[i].x+v[i].r>xx-k) une(i, m+3);
   ^~
park.cpp:40:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(v[i].x-v[i].r<k) une(i, m+2); if(v[i].x+v[i].r>xx-k) une(i, m+3);
                                    ^~
park.cpp:41:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(v[i].y-v[i].r<k) une(i, m); if(v[i].y+v[i].r>yy-k) une(i, m+1);
   ^~
park.cpp:41:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(v[i].y-v[i].r<k) une(i, m); if(v[i].y+v[i].r>yy-k) une(i, m+1);
                                  ^~
park.cpp: In function 'int main()':
park.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~
park.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &xx, &yy);
  ~~~~~^~~~~~~~~~~~~~~~~~~
park.cpp:67:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d %d %d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1569 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 1088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1569 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -