Submission #45404

#TimeUsernameProblemLanguageResultExecution timeMemory
45404grumpy_gordonPark (BOI16_park)C++17
100 / 100
832 ms55264 KiB
/* .:*+=%@@@@@@=-. .:=@#@@@#@@#######%==*. .-=####@######%*-.....:%##%. .*@###########%+:--........-%@- .*@##############@+--.........-:%- .+##################@==%%%%=+*:----+. .-@####################%++%@@@@@=+**%@@* .%###################@%%@@@###@%+:--%@@%. -@###################@%%%%*::*%++:-----=@+. -#####################@%=++++++*:-------.-=: .+####################@%++*::-:::--::*:::***=: .@#####################%=++*::::-:::++*=##@@#@- ..#####################@%%=++**:::::**+%@#@%%##-.. .%####################@@%=+++*+****::*=@######@. .=######################@%%==+==++**+=@%@##@###+:... -#######################@@@%%%===++=@@@%=++===*::--... -########################@@@@@@@%==%%=++==@@:::::*:--. ..:#########################@@@@@@%%======++++::-..:-.--... %#############################@###@%%@@%==%=%*----.--.::---. #############################################*-:*:-:---*---- . #############################################*--*--:---*---:-. #############################################+--::--::-*::-::. ###########################################+:*-.---.---.:---*-.. ###########################################**:-----------------. ##########################################@::**:--::::::--:::::- ###########################################:--:*:::::::::**::*+* ###########################################=:::***::::::**:::*+* ############################@@@@@@#########@+****::::********+++ ############################@%%%%%@@@@@@@###%+***::::::::***+==+ ############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+ #############################@%%%%%%%%%%@#####=::--------:*=%@%+ %###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%= ---------------------------------------------- -------------------------------------------- ---------------------------------------------- -------------------------------------------- ---------------------------------------------- o###########oo o##" ""##o o#" "## o#" "#o #" ## ## "## #" ## # ################### # # # # # # # # # # # # # #o # "#o ## "#o ## "#o o#" "#o ## "#o o#" "#ooo ooo#######oo ############### "######o o###"" "###o # ### o###o oooo ### oo####" o###**# #**# ############" ""##""""""""""########### # # oooooooo#"#** ## # # # # # ** ## # #o# #o# *****###ooo# ## ## o###o ## o##***## o########## #***#**##o o##" ""### #***##***# o#######o ### oo#### ##**####*# o##" ""#############"" ##****### ##" ## ##*##*### ## ### ##### ## ## ### # ## # ## ## # ## ## ## ### ## ###oo ### ""### ### ### */ #include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") //#pragma GCC target("avx,tune=native") //float __attribute__((aligned(32))) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int uint; ll sqr(ll x){ return x * x; } int mysqrt(ll x){ int l = 0, r = 1e9 + 1; while (r - l > 1){ int m = (l + r) / 2; if (m * (ll)m <= x) l = m; else r = m; } return l; } mt19937 rnd(1227); mt19937_64 rndll(12365); ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993; ll myrand(){ ll ZR = (XR * AR + YR * BR + CR) % MODR; XR = YR; YR = ZR; return ZR; } const int Mod = 1e9 + 7; int bpow(int x, int y){ if (y == 0) return 1; if (y == 1) return x; int ret = bpow(x, y >> 1); ret = (ret * (ll)ret) % Mod; if (y & 1) ret = (ret * (ll)x) % Mod; return ret; } int bdiv(int x, int y){ return (x * (ll)bpow(y, Mod - 2)) % Mod; } void setmin(int &x, int y){ x = min(x, y); } void setmax(int &x, int y){ x = max(x, y); } void setmin(ll &x, ll y){ x = min(x, y); } void setmax(ll &x, ll y){ x = max(x, y); } int gcd(int a, int b){ return a ? gcd(b % a, a) : b; } const ll llinf = 2e18 + 100; const double eps = 1e-9; const int maxn = 1e5 + 100, maxw = 1e7 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17; int n, w, h; pair<int, int> a[maxn]; int rad[maxn]; pair<ll, ll> getw(int i, int j){ if (i < 0 && j < 0) return make_pair(inf, inf); if (i < 0) swap(i, j); if (j == -1) return make_pair(sqr(a[i].second), rad[i]); if (j == -2) return make_pair(sqr(w - a[i].first), rad[i]); if (j == -3) return make_pair(sqr(h - a[i].second), rad[i]); if (j == -4) return make_pair(sqr(a[i].first), rad[i]); return make_pair(sqr(a[i].first - a[j].first) + sqr(a[i].second - a[j].second), rad[i] + rad[j]); } void precalc(){ } int p[maxn], rnk[maxn]; int get(int x){ return x == p[x] ? x : p[x] = get(p[x]); } void uni(int x, int y){ x = get(x); y = get(y); if (x == y) return; if (rnk[x] < rnk[y]) swap(x, y); p[y] = x; if (rnk[x] == rnk[y]) rnk[x]++; } int ae[4][4]; void add(int x, int y){ ae[x][y] = 1; ae[y][x] = 1; } string calc(int r, int t){ for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) ae[i][j] = 0; if (get(0) == get(1)) add(0, 3), add(1, 3), add(2, 3); if (get(0) == get(2)) add(0, 2), add(0, 3), add(1, 2), add(1, 3); if (get(0) == get(3)) add(0, 1), add(0, 2), add(0, 3); if (get(1) == get(2)) add(0, 2), add(1, 2), add(3, 2); if (get(1) == get(3)) add(0, 2), add(0, 1), add(3, 2), add(3, 1); if (get(2) == get(3)) add(0, 1), add(2, 1), add(3, 1); string ret; for (int i = 0; i < 4; i++) if (!ae[t][i]) ret.push_back(49 + i); return ret; } pair<pair<int, int>, int> que[maxn]; vector<pair<int, int> > g[maxn]; string ans[maxn]; int main() { #ifdef ONPC //ifstream cin("a.in"); //ofstream cout("a.out"); freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #else //ifstream cin("gymnasts.in"); //ofstream cout("gymnasts.out"); //freopen("sort.in", "r", stdin); //freopen("sort.out", "w", stdout); #endif // ONPC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int zap; cin >> n >> zap >> w >> h; for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second >> rad[i]; precalc(); for (int i = 0; i < zap; i++) cin >> que[i].first.first >> que[i].first.second, que[i].first.second--, que[i].second = i; sort(que, que + zap); for (int i = 0; i < n + 4; i++) p[i] = i, rnk[i] = 0; for (int i = 0; i < n + 4; i++) for (int j = 0; j < n + 4; j++){ pair<ll, ll> x = getw(i - 4, j - 4); int L = -1, R = zap; while (R - L > 1){ int m = (L + R) / 2; if (x != make_pair((ll)inf, (ll)inf) && x.first < sqr(x.second + 2 * que[m].first.first)) R = m; else L = m; } if (R < zap) g[R].push_back(make_pair(i, j)); } for (int i = 0; i < zap; i++){ for (auto j : g[i]) uni(j.first, j.second); ans[que[i].second] = calc(que[i].first.first, que[i].first.second); } for (int i = 0; i < zap; i++) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...