Submission #1263478

#TimeUsernameProblemLanguageResultExecution timeMemory
1263478rafamiunePark (BOI16_park)C++20
0 / 100
2563 ms576 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct Tree { int x, y, r; }; int n, w, h; vector<Tree> trees; vector<bool> mark; bool N, S, E, W; void dfs(int v, int visitor_r) { if(mark[v]) return; mark[v] = 1; int R = trees[v].r + visitor_r; if (trees[v].x - R <= 0) W = 1; if (trees[v].x + R >= w) E = 1; if (trees[v].y - R <= 0) S = 1; if (trees[v].y + R >= h) N = 1; for(int i = 0; i < n; i++) { if(mark[i]) continue; int dx = trees[i].x - trees[v].x; int dy = trees[i].y - trees[v].y; int sum = trees[i].r + trees[v].r + 2*visitor_r; if(dx*dx + dy*dy <= sum*sum) dfs(i, visitor_r); } } void solve(int visitor_r, int entry) { mark.assign(n, false); vector<bool> ok(5,true); // ok[1..4] = saídas possíveis for(int i = 0; i < n; i++) { if(mark[i]) continue; N = S = E = W = false; dfs(i, visitor_r); // Bloquear saídas conectadas à entrada if(entry==1 && W) ok[4]=false; if(entry==1 && N) ok[4]=false; if(entry==2 && N) ok[1]=false; if(entry==2 && E) ok[3]=false; if(entry==3 && E) ok[2]=false; if(entry==3 && S) ok[4]=false; if(entry==4 && S) ok[3]=false; if(entry==4 && W) ok[2]=false; // Note: dependendo da geometria, pode-se adicionar mais combinações } for(int i=1;i<=4;i++) if(ok[i]) cout<<i; cout<<"\n"; } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int m; cin >> n >> m >> w >> h; trees.resize(n); for(int i=0;i<n;i++) cin >> trees[i].x >> trees[i].y >> trees[i].r; while(m--) { int r, entry; cin >> r >> entry; solve(r, entry); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...