oj.uz

답안 #46282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46282 2018-04-18T18:04:03 Z ikura355 Park (BOI16_park) C++14
0 / 100
 2500 ms 1404 KB 
//aiming for 58 marks
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
struct point {
	double x, y, r;
};
int n,m;
double w,h;
point p[maxn];
int head[maxn];
int bad[10], con[10][10];
double cut(point x, point y) {
	return sqrt((x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y));
}
int findhead(int x) {
	if(head[x]==x) return x;
	return head[x] = findhead(head[x]);
}
int main() {
	scanf("%d%d%lf%lf",&n,&m,&w,&h);
	for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
	for(int tnum=1;tnum<=m;tnum++) {
		double fat; int ent;
		scanf("%lf%d",&fat,&ent); fat *= 2.0;
		for(int i=1;i<=n+4;i++) head[i] = i;
		//tree - tree
		for(int i=1;i<=n;i++) {
			for(int j=i+1;j<=n;j++) {
				if(cut(p[i],p[j])-p[i].r-p[j].r < fat) {
					head[findhead(i)] = findhead(j);
				}
			}
		}
		//tree - edge
		for(int i=1;i<=n;i++) {
			if(p[i].y-p[i].r < fat) head[findhead(i)] = findhead(n+1);
			if(w-p[i].x-p[i].r < fat) head[findhead(i)] = findhead(n+2);
			if(h-p[i].y-p[i].r < fat) head[findhead(i)] = findhead(n+3);
			if(p[i].x-p[i].r < fat) head[findhead(i)] = findhead(n+4);
		}
		//connection
		int id = 0;
		for(int i=n+1;i<=n+4;i++) {
			for(int j=i+1;j<=n+4;j++) {
				bad[++id] = findhead(i)==findhead(j);
			}
		}
        for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) con[i][j] = 1;
		if(bad[1] || bad[2] || bad[3]) con[1][2] = con[2][1] = 0;
		if(bad[2] || bad[3] || bad[4] || bad[5]) con[1][3] = con[3][1] = 0;
		if(bad[3] || bad[5] || bad[6]) con[1][4] = con[4][1] = 0;
		if(bad[1] || bad[4] || bad[5]) con[2][3] = con[3][2] = 0;
		if(bad[1] || bad[2] || bad[5] || bad[6]) con[2][4] = con[4][2] = 0;
		if(bad[2] || bad[4] || bad[5]) con[3][4] = con[4][3] = 0;
		//answer
		for(int i=1;i<=4;i++) if(con[ent][i]) printf("%d",i);
		printf("\n");
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lf%lf",&n,&m,&w,&h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:22:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%d",&fat,&ent); fat *= 2.0;
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 376 KB Output is correct
2 Incorrect 10 ms 548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2566 ms 1404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 376 KB Output is correct
2 Incorrect 10 ms 548 KB Output isn't correct
3 Halted 0 ms 0 KB -