oj.uz

Submission #64034

# Submission time Handle Problem Language Result Execution time Memory
64034 2018-08-03T08:33:35 Z 끄흐수(#2146) Park (BOI16_park) C++11
100 / 100
 537 ms 36956 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 378 ms 33468 KB Output is correct
2 Correct 388 ms 33468 KB Output is correct
3 Correct 368 ms 33504 KB Output is correct
4 Correct 395 ms 33504 KB Output is correct
5 Correct 384 ms 33504 KB Output is correct
6 Correct 358 ms 33504 KB Output is correct
7 Correct 348 ms 33512 KB Output is correct
8 Correct 355 ms 33512 KB Output is correct
9 Correct 2 ms 33512 KB Output is correct
10 Correct 3 ms 33512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 33512 KB Output is correct
2 Correct 90 ms 33512 KB Output is correct
3 Correct 99 ms 33512 KB Output is correct
4 Correct 89 ms 33512 KB Output is correct
5 Correct 126 ms 33512 KB Output is correct
6 Correct 101 ms 33512 KB Output is correct
7 Correct 90 ms 33512 KB Output is correct
8 Correct 88 ms 33512 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 33468 KB Output is correct
2 Correct 388 ms 33468 KB Output is correct
3 Correct 368 ms 33504 KB Output is correct
4 Correct 395 ms 33504 KB Output is correct
5 Correct 384 ms 33504 KB Output is correct
6 Correct 358 ms 33504 KB Output is correct
7 Correct 348 ms 33512 KB Output is correct
8 Correct 355 ms 33512 KB Output is correct
9 Correct 2 ms 33512 KB Output is correct
10 Correct 3 ms 33512 KB Output is correct
11 Correct 94 ms 33512 KB Output is correct
12 Correct 90 ms 33512 KB Output is correct
13 Correct 99 ms 33512 KB Output is correct
14 Correct 89 ms 33512 KB Output is correct
15 Correct 126 ms 33512 KB Output is correct
16 Correct 101 ms 33512 KB Output is correct
17 Correct 90 ms 33512 KB Output is correct
18 Correct 88 ms 33512 KB Output is correct
19 Correct 507 ms 36812 KB Output is correct
20 Correct 529 ms 36816 KB Output is correct
21 Correct 467 ms 36872 KB Output is correct
22 Correct 421 ms 36872 KB Output is correct
23 Correct 537 ms 36872 KB Output is correct
24 Correct 431 ms 36956 KB Output is correct