oj.uz

Submission #63986

# Submission time Handle Problem Language Result Execution time Memory
63986 2018-08-03T08:02:40 Z 끄흐수(#2146) Park (BOI16_park) C++11
0 / 100
 868 ms 263168 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2018, inf = 1e18;
const ll CA[6] = {1, 1, 1, 2, 2, 3};
const ll CB[6] = {2, 3, 4, 3, 4, 4};
const ll CC[6] = {2, 6, 1, 4, 3, 7};

ll n, m, w, h, x[N], y[N], r[N], p[N], ans[N];

struct event {
	ll a, b, c;
	bool operator < (event &T) {
		return (c < T.c);
	}
};

vector<event> act, qry;

int Find (int X) {
	if(p[X] == X) return X;
	return p[X] = Find(p[X]);
}

int getbit (int B, int C) {
	return (((1<<(C-1))&B) ? B : (~B & 15));
}

int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
	iota(p+1, p+1+n+4, 1);
	for(int i=5;i<=n+4;i++) {
		scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);
		for(ll j=5;j<i;j++) {
			ll T = (ceil(hypot(x[i]-x[j], y[i]-y[j]))-r[i]-r[j]+1)/2;
			act.push_back({i, j, T});
		}
		act.push_back({i, 1, (y[i]-r[i]+1)/2});
		act.push_back({i, 2, (w-x[i]-r[i]+1)/2});
		act.push_back({i, 3, (h-y[i]-r[i]+1)/2});
		act.push_back({i, 4, (x[i]-r[i]+1)/2});
	}
	act.push_back({1, 1, inf});
	for(int i=1;i<=m;i++) {
		event T;
		scanf("%lld%lld",&T.c,&T.b);
		T.a = i;
		ans[i] = 15;
		qry.push_back(T);
	}
	sort(act.begin(), act.end());
	sort(qry.begin(), qry.end());
	for(int i=0,j=0;i<(int)act.size();i++) {
		auto &T = act[i];
		for(;j<(int)qry.size() && qry[j].c < T.c; j++) {
			int I = qry[j].a, B = qry[j].b;
			for(int k=0;k<6;k++) {
				if(Find(CA[k]) == Find(CB[k])) {
					ans[I] &= getbit(CC[k], B);
				}
			}
		}
		p[Find(act[i].a)] = Find(act[i].b);
	}
	for(int i=1;i<=m;i++) {
		for(int j=0;j<4;j++) {
			if(ans[i] & (1<<j)) printf("%d",j+1);
		}
		puts("");
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld",&n,&m,&w,&h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&T.c,&T.b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 49836 KB Output is correct
2 Correct 473 ms 49948 KB Output is correct
3 Correct 413 ms 50056 KB Output is correct
4 Correct 414 ms 50056 KB Output is correct
5 Correct 470 ms 50056 KB Output is correct
6 Correct 506 ms 50056 KB Output is correct
7 Correct 377 ms 50056 KB Output is correct
8 Incorrect 352 ms 50056 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 868 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 49836 KB Output is correct
2 Correct 473 ms 49948 KB Output is correct
3 Correct 413 ms 50056 KB Output is correct
4 Correct 414 ms 50056 KB Output is correct
5 Correct 470 ms 50056 KB Output is correct
6 Correct 506 ms 50056 KB Output is correct
7 Correct 377 ms 50056 KB Output is correct
8 Incorrect 352 ms 50056 KB Output isn't correct
9 Halted 0 ms 0 KB -