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...