답안 #63852 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63852	2018-08-03T05:22:43 Z	윤교준(#1870)	Park (BOI16_park)	C++11	100 / 100	430 ms	31616 KB

park

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
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++) {
		//printf("co=%d, evi=%d\n", co, evi);
		for(; evi < sz(EV) && EV[evi].c == co; evi++) {
			uf(EV[evi].a, EV[evi].b);
			//printf("UF %d %d\n", 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.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	27464 KB	Output is correct
2	Correct	161 ms	27572 KB	Output is correct
3	Correct	139 ms	27648 KB	Output is correct
4	Correct	122 ms	27712 KB	Output is correct
5	Correct	142 ms	27712 KB	Output is correct
6	Correct	117 ms	27712 KB	Output is correct
7	Correct	148 ms	27712 KB	Output is correct
8	Correct	120 ms	27816 KB	Output is correct
9	Correct	6 ms	27816 KB	Output is correct
10	Correct	4 ms	27816 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	27816 KB	Output is correct
2	Correct	124 ms	27816 KB	Output is correct
3	Correct	125 ms	27816 KB	Output is correct
4	Correct	134 ms	27816 KB	Output is correct
5	Correct	134 ms	27816 KB	Output is correct
6	Correct	124 ms	27816 KB	Output is correct
7	Correct	107 ms	27816 KB	Output is correct
8	Correct	84 ms	27816 KB	Output is correct

Subtask #3
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	27464 KB	Output is correct
2	Correct	161 ms	27572 KB	Output is correct
3	Correct	139 ms	27648 KB	Output is correct
4	Correct	122 ms	27712 KB	Output is correct
5	Correct	142 ms	27712 KB	Output is correct
6	Correct	117 ms	27712 KB	Output is correct
7	Correct	148 ms	27712 KB	Output is correct
8	Correct	120 ms	27816 KB	Output is correct
9	Correct	6 ms	27816 KB	Output is correct
10	Correct	4 ms	27816 KB	Output is correct
11	Correct	124 ms	27816 KB	Output is correct
12	Correct	124 ms	27816 KB	Output is correct
13	Correct	125 ms	27816 KB	Output is correct
14	Correct	134 ms	27816 KB	Output is correct
15	Correct	134 ms	27816 KB	Output is correct
16	Correct	124 ms	27816 KB	Output is correct
17	Correct	107 ms	27816 KB	Output is correct
18	Correct	84 ms	27816 KB	Output is correct
19	Correct	306 ms	30852 KB	Output is correct
20	Correct	358 ms	31236 KB	Output is correct
21	Correct	365 ms	31236 KB	Output is correct
22	Correct	379 ms	31320 KB	Output is correct
23	Correct	416 ms	31616 KB	Output is correct
24	Correct	430 ms	31616 KB	Output is correct

답안 #63852

Compilation message

Subtask #1 27.0 / 27.0

Subtask #2 31.0 / 31.0

Subtask #3 42.0 / 42.0

Subtask #1
27.0 / 27.0

Subtask #2
31.0 / 31.0

Subtask #3
42.0 / 42.0