Submission #1299419

#TimeUsernameProblemLanguageResultExecution timeMemory
1299419Jawad_Akbar_JJPark (BOI16_park)C++20
27 / 100
2582 ms4420 KiB
#include <iostream>
#include <queue>

using namespace std;
#define int long long
const int N = 2005;
bool adj[N][N], seen[4][N];
int x[N], y[N], r[N], cur = 1;
int n, m, w, h;

void bfs(int s, int id){
  queue<int> Q; Q.push(s);
  seen[id][s] = 1;

  while (Q.size() > 0){
    s = Q.front();
    Q.pop();

    for (int i=1;i<=n;i++){
      if (seen[id][i] != 1 and adj[s][i])
        seen[id][i] = 1, Q.push(i);
    }
  }
}

int sq(int k){
  return k * k;
}

bool none(int a, int b, int c, int d, int e, int f, int g, int h){
  return (seen[a-1][b] + seen[c-1][d] + seen[e-1][f] + seen[g-1][h]) == 0;
}

string get(int rd, int num = 0){
  for (int i=5;i<=n;i++){
    if (x[i] < r[i] + 2 * rd){
      adj[2][i] = 1;
      adj[i][2] = 1;
    }
    if (w - x[i] < r[i] + 2 * rd){
      adj[3][i] = 1;
      adj[i][3] = 1;
    }
    if (y[i] < r[i] + 2 * rd){
      adj[4][i] = 1;
      adj[i][4] = 1;
    }
    if (h - y[i] < r[i] + 2 * rd){
      adj[1][i] = 1;
      adj[i][1] = 1;
    }
    
    for (int j=5;j<=n;j++){
      if (i != j and sq(rd + rd + r[i] + r[j]) > sq(x[i] - x[j]) + sq(y[i] - y[j]))
        adj[i][j] = 1;
    }
  }
  for (int i : {1, 2, 3, 4})
    bfs(i, i-1);

  string Ans = "01234";

  if (none(3, 4, 2, 4, 1, 4, 1, 4))
    Ans[2] = Ans[1];
  if (none(3, 1, 3, 2, 3, 4, 3, 4))
    Ans[3] = Ans[2];
  if (none(1, 3, 2, 4, 3, 2, 1, 4))
    Ans[3] = Ans[1];
  if (none(1, 2, 1, 3, 1, 4, 1, 4))
    Ans[4] = Ans[3];
  if (none(1, 2, 3, 4, 1, 4, 2, 3))
    Ans[4] = Ans[2];
  if (none(2, 1, 2, 3, 2, 4, 2, 4))
    Ans[4] = Ans[1];

  for (int i=0;i<N;i++){
    for (int j=0;j<N;j++)
      adj[i][j] = 0;
    for (int j=0;j<4;j++)
      seen[j][i] = 0;
  }
  return Ans;
}

signed main(){
  cin>>n>>m>>w>>h;

  n += 4;
  for (int i=5;i<=n;i++)
    cin>>x[i]>>y[i]>>r[i];

  for (int i=1;i<=m;i++){
    int rr, e;
    cin>>rr>>e;

    // for (int j=5;j<=n;j++){
    //   cout<<"(x - "<<x[j]<<") ^ 2 + (y - "<<y[j]<<") ^ 2 = "<<r[j] + rr<<" ^ 2"<<endl;
    // }

    string cur = get(rr);
    for (int k : {1, 2, 3, 4}){
      if (cur[k] == cur[e])
        cout<<k;
    }
    cout<<'\n';
  }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...