oj.uz

Submission #46284

# Submission time Handle Problem Language Result Execution time Memory
46284 2018-04-18T18:13:30 Z ikura355 Park (BOI16_park) C++14
27 / 100
 2500 ms 1284 KB 
//aiming for 58 marks
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
const double eps = 1e-7;
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));
}
bool noey(double x, double y) {
    return (y-x)>eps;
}
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(noey(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(noey(p[i].y-p[i].r, fat)) head[findhead(i)] = findhead(n+1);
			if(noey(w-p[i].x-p[i].r, fat)) head[findhead(i)] = findhead(n+2);
			if(noey(h-p[i].y-p[i].r, fat)) head[findhead(i)] = findhead(n+3);
			if(noey(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[6]) con[3][4] = con[4][3] = 0;
		//show
//		id = 0;
//		for(int i=1;i<=4;i++) {
//            for(int j=i+1;j<=4;j++) printf("bad %d %d = %d\n",i,j,bad[++id]);
//		}
		//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:25: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:26: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:29: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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 19 ms 684 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 12 ms 828 KB Output is correct
7 Correct 24 ms 916 KB Output is correct
8 Correct 11 ms 952 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 2 ms 952 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2560 ms 1284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 19 ms 684 KB Output is correct
4 Correct 11 ms 716 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 12 ms 828 KB Output is correct
7 Correct 24 ms 916 KB Output is correct
8 Correct 11 ms 952 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 2 ms 952 KB Output is correct
11 Execution timed out 2560 ms 1284 KB Time limit exceeded
12 Halted 0 ms 0 KB -