Submission #1263468

#TimeUsernameProblemLanguageResultExecution timeMemory
1263468rafamiunePark (BOI16_park)C++20
0 / 100
2595 ms3656 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second #define int long long #define all(x) (x).begin(), (x).end() const int maxn = 1e5 + 5; const long long inf = 1e18 + 5; int n, w, h; bool N, S, E, W; vector<int> x(maxn), y(maxn), r(maxn), mark(maxn); void dfs(int v, int radius) { stack<int> st; st.push(v); mark[v] = 1; while(!st.empty()) { int u = st.top(); st.pop(); if ((x[u] - r[u]) <= 2 * radius) W = 1; if ((w - x[u] - r[u]) <= 2 * radius) E = 1; if ((y[u] - r[u]) <= 2 * radius) S = 1; if ((h - y[u] - r[u]) <= 2 * radius) N = 1; for(int i = 1; i <= n; i++) { if(mark[i]) continue; int dx = x[i] - x[u], dy = y[i] - y[u]; __int128 dist2 = (__int128)dx*dx + (__int128)dy*dy; int sum = r[u] + r[i] + 2*radius; if (dist2 <= (__int128)sum*sum) { mark[i] = 1; st.push(i); } } } } void solve(int radius, int exit) { for(int i = 1; i <= n; i++) mark[i] = 0; bool ok1 = 1, ok2 = 1, ok3 = 1, ok4 = 1; for(int i = 1; i <= n; i++) { if(mark[i]) continue; N = S = E = W = 0; dfs(i, radius); if (exit == 1) { if (W && N) ok4 = 0; if (W && E) { ok4 = 0; ok3 = 0; } if (W && S) { ok4 = 0; ok3 = 0; ok2 = 0; } if (S && N) { ok2 = 0; ok3 = 0; } if (S && E) ok2 = 0; if (N && E) ok3 = 0; } if (exit == 2) { if (W && N) ok4 = 0; if (W && E) { ok4 = 0; ok3 = 0; } if (W && S) ok1 = 0; if (S && N) { ok1 = 0; ok4 = 0; } if (S && E) { ok1 = 0; ok3 = 0; ok4 = 0; } if (N && E) ok3 = 0; } if (exit == 3) { if (W && N) ok4 = 0; if (W && E) { ok1 = 0; ok2 = 0; } if (W && S) ok1 = 0; if (S && N) { ok4 = 0; ok1 = 0; } if (S && E) ok2 = 0; if (N && E) { ok1 = 0; ok2 = 0; ok4 = 0; } } if (exit == 4) { if (W && N) { ok1 = 0; ok2 = 0; ok3 = 0; } if (W && E) { ok1 = 0; ok2 = 0; } if (W && S) ok1 = 0; if (S && N) { ok2 = 0; ok3 = 0; } if (S && E) ok2 = 0; if (N && E) ok3 = 0; } } if(ok1) cout << 1; if(ok2) cout << 2; if(ok3) cout << 3; if(ok4) cout << 4; cout << "\n"; } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int m; cin >> n >> m >> w >> h; for(int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> r[i]; } while(m--) { int a, b; cin >> a >> b; solve(a, b); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...