Submission #98768

#	Time	Username	Problem	Language	Result	Execution time	Memory
98768		youngyojun	Park (BOI16_park)	C++11	100 / 100	352 ms	32464 KiB

park

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<int, int> pii;
ll pw(ll n) { return n*n; }
lll pwlll(lll n) { return n*n; }
ll dst(const pii &a, const pii &b) { return pw(a.first-b.first) + pw(a.second-b.second); }
 
const int MAXN = 2055;
const int MAXK = 100055;
 
struct EVT {
	EVT(int a, int b, int c) : a(a), b(b), c(c) {}
	int a, b, c;
 
	bool operator < (const EVT &t) const { return c < t.c; }
};
 
vector<pii> KEYV[5][5];
 
vector<EVT> EV;
vector<int> CV, CO[MAXK];
 
int ud[MAXN];
 
int C[MAXK], D[MAXK], CI[MAXK];
pii A[MAXN]; int B[MAXN];
 
int Ans[MAXK];
 
int W, H, N, K;
 
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
 
int main() {
	ios::sync_with_stdio(false);
	iota(ud, ud+MAXN, 0);
 
	cin >> N >> K >> W >> H;
	for(int i = 1; i <= N; i++)
		cin >> A[i].first >> A[i].second >> B[i];
	for(int i = 1; i <= K; i++) {
		cin >> C[i] >> D[i];
		CV.eb(C[i]);
	}
	sorv(CV); univ(CV);
	for(int i = 1; i <= K; i++) {
		CI[i] = int(lower_bound(allv(CV), C[i]) - CV.begin());
		CO[CI[i]].eb(i);
	}
	
	for(int i = 1; i <= N; i++) for(int j = i+1; j <= N; j++) {
		ll l = dst(A[i], A[j]);
		int s = 0, e = sz(CV); for(int m; s < e;) {
			m = (s+e) >> 1;
			if(lll(l) < pwlll(ll(CV[m]) * 2 + B[i] + B[j])) e = m;
			else s = m+1;
		}
		EV.eb(i, j, s);
	}
	for(int i = 1; i <= N; i++) {
		int l = A[i].second - B[i];
		int s = 0, e = sz(CV); for(int m; s < e;) {
			m = (s+e) >> 1;
			if(l < CV[m]*2) e = m;
			else s = m+1;
		}
		EV.eb(i, N+1, s);
	}
	for(int i = 1; i <= N; i++) {
		int l = W - A[i].first - B[i];
		int s = 0, e = sz(CV); for(int m; s < e;) {
			m = (s+e) >> 1;
			if(l < CV[m]*2) e = m;
			else s = m+1;
		}
		EV.eb(i, N+2, s);
	}
	for(int i = 1; i <= N; i++) {
		int l = H - A[i].second - B[i];
		int s = 0, e = sz(CV); for(int m; s < e;) {
			m = (s+e) >> 1;
			if(l < CV[m]*2) e = m;
			else s = m+1;
		}
		EV.eb(i, N+3, s);
	}
	for(int i = 1; i <= N; i++) {
		int l = A[i].first - B[i];
		int s = 0, e = sz(CV); for(int m; s < e;) {
			m = (s+e) >> 1;
			if(l < CV[m]*2) e = m;
			else s = m+1;
		}
		EV.eb(i, N+4, s);
	}
	sorv(EV);
 
	{
		KEYV[1][2].eb(N+1, N+2); KEYV[1][2].eb(N+1, N+3); KEYV[1][2].eb(N+1, N+4);
		KEYV[2][3].eb(N+2, N+1); KEYV[2][3].eb(N+2, N+3); KEYV[2][3].eb(N+2, N+4);
		KEYV[3][4].eb(N+3, N+1); KEYV[3][4].eb(N+3, N+2); KEYV[3][4].eb(N+3, N+4);
		KEYV[1][4].eb(N+4, N+1); KEYV[1][4].eb(N+4, N+2); KEYV[1][4].eb(N+4, N+3);
 
		KEYV[1][3].eb(N+1, N+3); KEYV[1][3].eb(N+1, N+4); KEYV[1][3].eb(N+2, N+3); KEYV[1][3].eb(N+2, N+4);
		KEYV[2][4].eb(N+1, N+2); KEYV[2][4].eb(N+1, N+3); KEYV[2][4].eb(N+4, N+2); KEYV[2][4].eb(N+4, N+3);
	}
	for(int co = 0, evi = 0; co < K; co++) {
		for(; evi < sz(EV) && EV[evi].c == co; evi++) {
			uf(EV[evi].a, EV[evi].b);
		}
 
		for(int v : CO[co]) {
			int t = D[v];
			Ans[v] |= 1<<t;
			for(int a = 1; a <= 4; a++) for(int b = a+1; b <= 4; b++) {
				if(a != t && b != t) continue;
				bool flag = false;
				for(auto &p : KEYV[a][b]) {
					if(uf(p.first) == uf(p.second)) {
						flag = true;
						break;
					}
				}
				if(!flag) Ans[v] |= 1<<a | 1<<b;
			}
		}
	}
 
	for(int i = 1; i <= K; i++) {
		for(int j = 1; j <= 4; j++)
			if(Ans[i] & (1<<j)) printf("%d", j);
		puts("");
	}
	return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42