oj.uz

Submission #64076

# Submission time Handle Problem Language Result Execution time Memory
64076 2018-08-03T10:16:45 Z khsoo01 Park (BOI16_park) C++11
100 / 100
 461 ms 52296 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll N = 2018, M = 100005, 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[M];
 
struct event {
	int a, b;
	ll 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(int j=5;j<i;j++) {
			ll T = floor(hypot(x[i]-x[j], y[i]-y[j]))-r[i]-r[j]+1;
			act.push_back({i, j, T});
		}
		act.push_back({i, 1, y[i]-r[i]+1});
		act.push_back({i, 2, w-x[i]-r[i]+1});
		act.push_back({i, 3, h-y[i]-r[i]+1});
		act.push_back({i, 4, x[i]-r[i]+1});
	}
	act.push_back({1, 1, inf});
	for(int i=1;i<=m;i++) {
		event T;
		scanf("%lld%d",&T.c,&T.b);
		T.c *= 2;
		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++) {
			ll 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(T.a)] = Find(T.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:33: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:36: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:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%d",&T.c,&T.b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 33468 KB Output is correct
2 Correct 393 ms 33636 KB Output is correct
3 Correct 367 ms 33636 KB Output is correct
4 Correct 395 ms 33680 KB Output is correct
5 Correct 394 ms 33924 KB Output is correct
6 Correct 362 ms 33924 KB Output is correct
7 Correct 321 ms 33924 KB Output is correct
8 Correct 302 ms 33976 KB Output is correct
9 Correct 2 ms 33976 KB Output is correct
10 Correct 2 ms 33976 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 33976 KB Output is correct
2 Correct 64 ms 33976 KB Output is correct
3 Correct 64 ms 33976 KB Output is correct
4 Correct 65 ms 33976 KB Output is correct
5 Correct 67 ms 33976 KB Output is correct
6 Correct 70 ms 33976 KB Output is correct
7 Correct 58 ms 33976 KB Output is correct
8 Correct 60 ms 33976 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 33468 KB Output is correct
2 Correct 393 ms 33636 KB Output is correct
3 Correct 367 ms 33636 KB Output is correct
4 Correct 395 ms 33680 KB Output is correct
5 Correct 394 ms 33924 KB Output is correct
6 Correct 362 ms 33924 KB Output is correct
7 Correct 321 ms 33924 KB Output is correct
8 Correct 302 ms 33976 KB Output is correct
9 Correct 2 ms 33976 KB Output is correct
10 Correct 2 ms 33976 KB Output is correct
11 Correct 119 ms 33976 KB Output is correct
12 Correct 64 ms 33976 KB Output is correct
13 Correct 64 ms 33976 KB Output is correct
14 Correct 65 ms 33976 KB Output is correct
15 Correct 67 ms 33976 KB Output is correct
16 Correct 70 ms 33976 KB Output is correct
17 Correct 58 ms 33976 KB Output is correct
18 Correct 60 ms 33976 KB Output is correct
19 Correct 428 ms 47020 KB Output is correct
20 Correct 419 ms 48052 KB Output is correct
21 Correct 423 ms 49004 KB Output is correct
22 Correct 450 ms 49992 KB Output is correct
23 Correct 461 ms 51140 KB Output is correct
24 Correct 441 ms 52296 KB Output is correct