제출 #256916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256916		Nightlight	Park (BOI16_park)	C++14	100 / 100	403 ms	33400 KiB

park

#include <bits/stdc++.h>
#define P2(n) ((n) * (n))
#define LEFT 2001
#define RIGHT 2002
#define UP 2003
#define DOWN 2004
#define piii tuple<long long, int, int> 
using namespace std;

int N, M;
long long H, W;
long long X[2005], Y[2005], R[2005];
int par[2010];
long long ans[10][10];
piii seg[10000005];
int p;

inline long long dist(int i, int j) {
  long long A = P2(X[i] - X[j]) + P2(Y[i] - Y[j]), B = sqrt(A);
  return B + 1;
}

int findpar(int u) {
  return par[u] == u ? u : par[u] = findpar(par[u]);
}

void merge(int u, int v) {
  u = findpar(u), v = findpar(v);
  if(u == v) return;
  par[v] = u;
}

int main() {
  for(int i = 1; i <= 4; i++) {
    for(int j = 1; j <= 4; j++) {
      ans[i][j] = LLONG_MAX;
    }
  }
  for(int i = 1; i <= 2005; i++) par[i] = i;
  scanf("%d %d", &N, &M);
  scanf("%lld %lld", &W, &H);
  for(int i = 1; i <= N; i++) {
    scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
    for(int j = 1; j < i; j++) {
      seg[++p] = {dist(i, j) - R[i] - R[j], i, j};
    }
    seg[++p] = {H - Y[i] - R[i], UP, i};
    seg[++p] = {Y[i] - R[i], DOWN, i};
    seg[++p] = {W - X[i] - R[i], RIGHT, i};
    seg[++p] = {X[i] - R[i], LEFT, i};
  }
  sort(seg + 1, seg + p + 1);
  long long now;
  int u, v;
  for(int i = 1; i <= p; i++) {
    tie(now, u, v) = seg[i];
    merge(u, v);
    
    if(findpar(UP) == findpar(DOWN)) {
      ans[1][2] = min(ans[1][2], now);
      ans[1][3] = min(ans[1][3], now);
      ans[4][2] = min(ans[4][2], now);
      ans[4][3] = min(ans[4][3], now);
    }

    if(findpar(LEFT) == findpar(RIGHT)) {
      ans[1][3] = min(ans[1][3], now);
      ans[1][4] = min(ans[1][4], now);
      ans[2][3] = min(ans[2][3], now);
      ans[2][4] = min(ans[2][4], now);
    }

    if(findpar(LEFT) == findpar(DOWN)) {
      ans[1][2] = min(ans[1][2], now);
      ans[1][3] = min(ans[1][3], now);
      ans[1][4] = min(ans[1][4], now);
    }

    if(findpar(DOWN) == findpar(RIGHT)) {
      ans[2][1] = min(ans[2][1], now);
      ans[2][3] = min(ans[2][3], now);
      ans[2][4] = min(ans[2][4], now);
    }

    if(findpar(RIGHT) == findpar(UP)) {
      ans[3][1] = min(ans[3][1], now);
      ans[3][2] = min(ans[3][2], now);
      ans[3][4] = min(ans[3][4], now);
    }

    if(findpar(UP) == findpar(LEFT)) {
      ans[4][1] = min(ans[4][1], now);
      ans[4][2] = min(ans[4][2], now);
      ans[4][3] = min(ans[4][3], now);
    }
  }
  int st;
  for(int i = 1; i <= 4; i++) {
    for(int j = 1; j <= 4; j++) {
      ans[i][j] = min(ans[i][j], ans[j][i]);
//      cout << i << " " << j << " -> " << ans[i][j] << "\n";
    }
  }
//  cout << dist(1, 2) << "\n";
  long long qR;
  while(M--) {
    scanf("%lld %d", &qR, &st);
    qR *= 2;
//    cout << qR << " -> ";
    for(int i = 1; i <= 4; i++) {
      if(qR < ans[st][i]) cout << i;
    }
    putchar('\n');
  }
  cin >> N;
} 

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int main()':
park.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
park.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &W, &H);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
park.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %d", &qR, &st);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42