Submission #584640

#	Time	Username	Problem	Language	Result	Execution time	Memory
584640		MilosMilutinovic	Drzava (COCI15_drzava)	C++14	160 / 160	894 ms	54336 KiB

drzava

/**
 *    author:  wxhtzdy
 *    created: 27.06.2022 18:47:13
**/
#include <bits/stdc++.h>

using namespace std;

struct point {
  int x, y, c;

  bool const 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 = a.x - b.x;
  long long dy = a.y - b.y;
  return dx * dx + dy * dy;
}

int readint(){
  int x=0,f=1; char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}

point a[50000];

int main() {
  int n, k;
  n = readint();
  k = readint();
  for (int i = 0; i < n; i++) {
    a[i].x = readint();
    a[i].y = readint();
    a[i].c = readint();
    a[i].c %= k;
  }
  sort(a, a + n);
  vector<vector<int>> g(n);
  auto Check = [&](long long x) {
    int d = (double) (sqrt(x) + 1);
    for (int i = 0; i < n; i++) {
      g[i].clear();
    }
    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) {
          g[i].push_back(j);
          g[j].push_back(i);
        }
        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++) {
          if ((int) que.size() >= k) {
            return true;
          }
          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) {
          vector<bool> new_dp(k + 1);
          for (int p = k; p >= 0; p--) {
            new_dp[p] = (dp[p] | dp[(((p - a[j].c) % k) + k) % k]);
          }
          swap(new_dp, dp);
          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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8
• Subtask 15: 8 / 8
• Subtask 16: 8 / 8
• Subtask 17: 8 / 8
• Subtask 18: 8 / 8
• Subtask 19: 8 / 8
• Subtask 20: 8 / 8