oj.uz

Submission #256999

# Submission time Handle Problem Language Result Execution time Memory
256999 2020-08-03T13:46:38 Z rama_pang Park (BOI16_park) C++14
31 / 100
 2500 ms 1792 KB 
#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 public:
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int sz) : p(sz) {
    iota(begin(p), end(p), 0);
  }
  void Clear() {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) {
      p[x] = y;
      return 1;
    }
    return 0;
  }
  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, Q, H, W;
  cin >> N >> Q >> W >> H;
  vector<long long> X(N), Y(N), R(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> R[i];
  }

  vector<long long> blocks(6);
  // blocks[0] = cover left to down
  // blocks[1] = cover down to right
  // blocks[2] = cover right to up
  // blocks[3] = cover up to left
  // blocks[4] = cover left to right
  // blocks[5] = cover up to down
  
  auto IsConnected = [&](long long rad, const function<bool(long long, long long)> &GA, 
                                        const function<bool(long long, long long)> &GB) -> bool {
    static DisjointSet D(N + 2);
    D.Clear();
    auto AddEdge = [&](int u, int v) {
      D.Unite(u, v);
    };
    for (int i = 0; i < N; i++) {
      if (GA(X[i] - 2ll * rad - R[i], Y[i]) || GA(X[i] + 2ll * rad + R[i], Y[i]) || 
          GA(X[i], Y[i] - 2ll * rad - R[i]) || GA(X[i], Y[i] + 2ll * rad + R[i])) {
        AddEdge(N + 0, i);
        if (D.SameSet(N, N + 1)) {
          return true;
        }
      }
      if (GB(X[i] - 2ll * rad - R[i], Y[i]) || GB(X[i] + 2ll * rad + R[i], Y[i]) || 
          GB(X[i], Y[i] - 2ll * rad - R[i]) || GB(X[i], Y[i] + 2ll * rad + R[i])) {
        AddEdge(N + 1, i);
        if (D.SameSet(N, N + 1)) {
          return true;
        }
      }
    }
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if ((X[i] - X[j]) * (X[i] - X[j]) + 
            (Y[i] - Y[j]) * (Y[i] - Y[j]) < 
            (R[i] + R[j] + 2ll * rad) * (R[i] + R[j] + 2ll * rad)) {
          AddEdge(i, j);
          if (D.SameSet(N, N + 1)) {
            return true;
          }
        }
      }
    }
    return false;
  };

  auto Solve = [&](const function<bool(long long, long long)> &GA, const function<bool(long long, long long)> &GB) -> long long {
    long long lo = 0, hi = 1e9;
    while (lo < hi) {
      long long md = (lo + hi) / 2;
      if (IsConnected(md, GA, GB)) {
        hi = md;
      } else {
        lo = md + 1;
      }
    }
    return lo;
  };

  blocks[0] = Solve([&](long long x, long long y) { return x < 0; }, [&](long long x, long long y) { return y < 0; });
  blocks[1] = Solve([&](long long x, long long y) { return y < 0; }, [&](long long x, long long y) { return x > W; });
  blocks[2] = Solve([&](long long x, long long y) { return x > W; }, [&](long long x, long long y) { return y > H; });
  blocks[3] = Solve([&](long long x, long long y) { return y > H; }, [&](long long x, long long y) { return x < 0; });
  blocks[4] = Solve([&](long long x, long long y) { return x < 0; }, [&](long long x, long long y) { return x > W; });
  blocks[5] = Solve([&](long long x, long long y) { return y < 0; }, [&](long long x, long long y) { return y > H; });

  while (Q--) {
    int r, e;
    cin >> r >> e;
    e--;
    string ans;
    for (int i = 0; i < 4; i++) {
      long long b = min(blocks[e], blocks[i]);
      if (((e == 0 || e == 1) && (i == 2 || i == 3)) || ((i == 0 || i == 1) && (e == 2 || e == 3))) {
        b = min(b, blocks[4]);
      }
      if (((e == 0 || e == 3) && (i == 1 || i == 2)) || ((i == 0 || i == 3) && (e == 1 || e == 2))) {
        b = min(b, blocks[5]);
      }
      if (e == i || r < b) {
        ans.push_back('1' + i);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 620 KB Output is correct
2 Correct 820 ms 504 KB Output is correct
3 Correct 756 ms 492 KB Output is correct
4 Correct 830 ms 632 KB Output is correct
5 Correct 787 ms 504 KB Output is correct
6 Correct 801 ms 504 KB Output is correct
7 Correct 2184 ms 512 KB Output is correct
8 Execution timed out 2572 ms 504 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1784 KB Output is correct
2 Correct 47 ms 1784 KB Output is correct
3 Correct 44 ms 1656 KB Output is correct
4 Correct 47 ms 1784 KB Output is correct
5 Correct 47 ms 1788 KB Output is correct
6 Correct 58 ms 1784 KB Output is correct
7 Correct 36 ms 1792 KB Output is correct
8 Correct 41 ms 1784 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 620 KB Output is correct
2 Correct 820 ms 504 KB Output is correct
3 Correct 756 ms 492 KB Output is correct
4 Correct 830 ms 632 KB Output is correct
5 Correct 787 ms 504 KB Output is correct
6 Correct 801 ms 504 KB Output is correct
7 Correct 2184 ms 512 KB Output is correct
8 Execution timed out 2572 ms 504 KB Time limit exceeded
9 Halted 0 ms 0 KB -