oj.uz

Submission #584629

# Submission time Handle Problem Language Result Execution time Memory
584629 2022-06-27T17:42:39 Z MilosMilutinovic Drzava (COCI15_drzava) C++14
104 / 160
 955 ms 51668 KB 
/**
 *    author:  wxhtzdy
 *    created: 27.06.2022 18:47:13
**/
#include <bits/stdc++.h>

using namespace std;

struct point {
  int x, y, c;

  bool operator < (const point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  };
};

long long Dist(point a, point b) {
  long long dx = abs(a.x - b.x);
  long long dy = abs(a.y - b.y);
  return dx * dx + dy * dy;
}

point a[50000];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, k;
  cin >> n >> k;     
  for (int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y >> a[i].c;
    a[i].c %= k;
  }
  sort(a, a + n);
  if (n <= 1000) {
    vector<tuple<long long, int, int>> edges;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        edges.push_back(make_tuple(Dist(a[i], a[j]), i, j));
      }
    }
    sort(edges.begin(), edges.end());
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> root = [&](int x) {
      return p[x] == x ? x : (p[x] = root(p[x]));
    };
    vector<vector<int>> ch(n);
    for (int i = 0; i < n; i++) {
      ch[i].push_back(i);
    }
    auto Unite = [&](int x, int y) {
      x = root(x);
      y = root(y);
      if (x == y) {
        return false;
      }        
      p[y] = x;
      for (int i : ch[y]) {
        ch[x].push_back(i);
      }                             
      ch[y].clear();
      if ((int) ch[x].size() >= k) {
        return true;
      }
      vector<bool> dp(k + 1);
      dp[0] = true;
      for (int i : ch[x]) {
        for (int p = k; p >= a[i].c; p--) {
          dp[p] = (dp[p] | dp[p - a[i].c]);
        }
        if (dp[k]) {
          return true;
        }
      }
      return false;
    };
    for (int i = 0; i < (int) edges.size(); i++) {
      if (Unite(get<1>(edges[i]), get<2>(edges[i]))) {
        long long d = get<0>(edges[i]);
        cout << fixed << setprecision(3) << sqrt(d) << '\n';
        return 0;
      }
    }       
    assert(false);
    return 0;
  }
  auto Check = [&](long long x) {
    int d = (double) (sqrt(x) + 1);
    vector<vector<int>> g(n);
    auto Add = [&](int x, int y) {
      g[x].push_back(y);
      g[y].push_back(x);
    };
    set<pair<int, int>> s;
    int ptr = 0;
    for (int i = 0; i < n; i++) {
      while (ptr < i && a[ptr].x + d < a[i].x) {
        s.erase(s.find(make_pair(a[ptr].y, ptr)));  
        ptr += 1;
      }               
      auto it = s.lower_bound(make_pair(a[i].y - d, -1));
      int cnt = 0;
      while (it != s.end()) {
        int j = it->second;
        if (abs(a[i].y - a[j].y) > d) {
          break;
        }
        cnt += 1;
        if (cnt >= 8 * k) {
          return true;
        }  
        if (Dist(a[i], a[j]) <= x) {
          Add(i, j);
        }
        it = next(it);   
      }
      s.emplace(a[i].y, i);
    }                    
    vector<bool> was(n);
    for (int i = 0; i < n; i++) {
      if (!was[i]) {
        vector<int> que(1, i);
        was[i] = true;
        for (int b = 0; b < (int) que.size(); b++) {
          int j = que[b];
          for (int p : g[j]) {
            if (!was[p]) {
              was[p] = true;
              que.push_back(p);
            }
          }
        }
        vector<bool> dp(k + 1, false);
        dp[0] = true;
        for (int j : que) {
          for (int p = k; p >= a[j].c; p--) {
            dp[p] = (dp[p] | dp[p - a[j].c]);
          }
          if (dp[k]) {
            return true;
          }
        }
      }
    }
    return false;
  };
  long long low = 0, high = 1e18, ans = 0;
  while (low <= high) {
    long long mid = low + high >> 1;
    if (Check(mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  cout << fixed << setprecision(3) << sqrt(ans * 1.0) << '\n';
  return 0;
}

Compilation message

drzava.cpp: In function 'int main()':
drzava.cpp:150:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |     long long mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 17 ms 4556 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 39 ms 8648 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 4556 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 955 ms 51668 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 907 ms 50936 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 598 ms 26428 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 657 ms 30588 KB Output is correct

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 298 ms 7228 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 435 ms 18764 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 459 ms 21760 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 468 ms 21836 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 371 ms 12716 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 316 ms 8936 KB Output is correct