Submission #64076

#	Time	Username	Problem	Language	Result	Execution time	Memory
64076		khsoo01	Park (BOI16_park)	C++11	100 / 100	461 ms	52296 KiB

park

#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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42