oj.uz

Submission #63842

# Submission time Handle Problem Language Result Execution time Memory
63842 2018-08-03T05:11:11 Z 윤교준(#1870) Park (BOI16_park) C++11
0 / 100
 138 ms 27636 KB 
#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(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]) 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]) 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]) 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]) 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 27464 KB Output is correct
2 Correct 121 ms 27604 KB Output is correct
3 Incorrect 138 ms 27636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 27636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 27464 KB Output is correct
2 Correct 121 ms 27604 KB Output is correct
3 Incorrect 138 ms 27636 KB Output isn't correct
4 Halted 0 ms 0 KB -