oj.uz

Submission #256916

# Submission time Handle Problem Language Result Execution time Memory
256916 2020-08-03T11:55:20 Z Nightlight Park (BOI16_park) C++14
100 / 100
 403 ms 33400 KB 
#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;
}

Compilation message

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 31992 KB Output is correct
2 Correct 340 ms 31900 KB Output is correct
3 Correct 331 ms 31864 KB Output is correct
4 Correct 340 ms 31992 KB Output is correct
5 Correct 334 ms 31872 KB Output is correct
6 Correct 340 ms 31896 KB Output is correct
7 Correct 282 ms 31992 KB Output is correct
8 Correct 270 ms 31992 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2040 KB Output is correct
2 Correct 44 ms 2040 KB Output is correct
3 Correct 45 ms 2168 KB Output is correct
4 Correct 50 ms 2092 KB Output is correct
5 Correct 44 ms 2040 KB Output is correct
6 Correct 46 ms 2168 KB Output is correct
7 Correct 40 ms 1784 KB Output is correct
8 Correct 44 ms 1784 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 31992 KB Output is correct
2 Correct 340 ms 31900 KB Output is correct
3 Correct 331 ms 31864 KB Output is correct
4 Correct 340 ms 31992 KB Output is correct
5 Correct 334 ms 31872 KB Output is correct
6 Correct 340 ms 31896 KB Output is correct
7 Correct 282 ms 31992 KB Output is correct
8 Correct 270 ms 31992 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 48 ms 2040 KB Output is correct
12 Correct 44 ms 2040 KB Output is correct
13 Correct 45 ms 2168 KB Output is correct
14 Correct 50 ms 2092 KB Output is correct
15 Correct 44 ms 2040 KB Output is correct
16 Correct 46 ms 2168 KB Output is correct
17 Correct 40 ms 1784 KB Output is correct
18 Correct 44 ms 1784 KB Output is correct
19 Correct 403 ms 33232 KB Output is correct
20 Correct 378 ms 33400 KB Output is correct
21 Correct 377 ms 33272 KB Output is correct
22 Correct 376 ms 33112 KB Output is correct
23 Correct 369 ms 33148 KB Output is correct
24 Correct 317 ms 33272 KB Output is correct