Submission #381001

#	Time	Username	Problem	Language	Result	Execution time	Memory
381001		alrad	Drzava (COCI15_drzava)	C++17	72 / 160	1095 ms	10784 KiB

drzava

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;
using ld = long double;
using ll = long long;

/*
#pragma comment(linker, "/STACK:256000000")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

template <class T> inline T gcd(T a , T b) { return !a ? b : gcd(b % a , a); }
template <class T> inline T lcm(T a , T b) { return (a * b) / gcd(a , b) ; }

mt19937 rnd(time(0));

#define all(x) x.begin(), x.end()
#define debug(x) { cerr << #x << " = " << x << endl; }

const int N = 50001;
const int MAXK = 30;
const int BL = 100;

int n, K;

struct Point {
  int x, y;
  int val, id;
  Point(int _x, int _y, int _val, int _id) {
    x = _x;
    y = _y;
    val = _val;
    id = _id;
  }
};

bool comp(const Point &p1, const Point &p2) {
  return (p1.x != p2.x ? p1.x < p2.x : p1.y < p2.y);
}

ll dist(const Point &p1, const Point &p2) {
  return ((p1.x - p2.x) * 1ll * (p1.x - p2.x) + (p1.y - p2.y) * 1ll * (p1.y - p2.y));
}

struct Edge {
  int u, v;
  long long W;
  Edge(int _u, int _v, ll _w) {
    u = _u;
    v = _v;
    W = _w;
  }
};

bool comp1(const Edge &e1, const Edge &e2) {
  return (e1.W < e2.W);
}

vector<Point> pts;
bool ost[N][MAXK];
vector<int> parent(N, -1);
vector<vector<int>> components(N, vector<int>());

int safe(int x) {
  return (x < 0 ? x + K : x);
}

int findSet(int v) {
  return parent[v];
}

void upd(int v, int val) {
  vector<bool> cnt(K, false);
  for (int i = 0; i < K; i++) {
    if (ost[v][i] || val == i || ost[v][safe(i - val)]) {
      cnt[i] = true;
    } else {
      cnt[i] = false;
    }
  }
  for (int i = 0; i < K; i++) {
    ost[v][i] = cnt[i];
  }
  return;
}

void unite(int a, int b) {
  a = findSet(a);
  b = findSet(b);
  if (a != b) {
    // b -> small
    if ((int)components[a].size() < (int)components[b].size()) {
      swap(a, b);
    }
    for (int cur : components[b]) {
      parent[cur] = a;
      components[a].push_back(cur);
      upd(a, pts[cur].val);
    }
    components[b].clear();
  }
}

void solve() {
  cin >> n >> K;
  for (int i = 0; i < n; i++) {
    int x, y, val;
    cin >> x >> y >> val;
    val %= K;
    pts.push_back(Point(x, y, val, i));
  }
  sort(all(pts), comp);
  vector<vector<int>> close(n, vector<int>());
  for (int i = 0; i < n; i++) {
    set<pair<long long, int>> q;
    for (int j = max(i - BL, 0); j < i; j++) {
      q.insert({dist(pts[i], pts[j]), j});
    }
    for (int j = i + 1; j < min(n, i + BL); j++) {
      q.insert({dist(pts[i], pts[j]), j});
    }
    for (auto it : q) {
      if ((int)close[i].size() >= K) {
        break;
      }
      close[i].push_back(it.second);
    }
  }
//  for (int i = 0; i < n; i++) {
//    cerr << "For pts #" << i + 1 << " ";
//    for (auto it : close[i]) {
//      cout << it + 1 << " ";
//    }
//    cout << '\n';
//  }
  for (int i = 0; i < n; i++) {
    parent[i] = i;
    components[i].push_back(i);
    ost[i][pts[i].val] = true;
  }
  vector<Edge> edges;
  for (int i = 0; i < n; i++) {
    for (int j : close[i]) {
      edges.push_back(Edge(i, j, dist(pts[i], pts[j])));
    }
  }
  sort(all(edges), comp1);
  for (auto e : edges) {
    unite(e.u, e.v);
    if (ost[findSet(e.u)][0]) {
      cout << fixed << setprecision(3) << sqrt(e.W) << '\n';
      return;
    }
  }
  assert(false);
  return;
}

signed main() {
  ios_base :: sync_with_stdio(0);
  cin.tie(0) , cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

• 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: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8
• Subtask 14: 0 / 8
• Subtask 15: 0 / 8
• Subtask 16: 0 / 8
• Subtask 17: 0 / 8
• Subtask 18: 0 / 8
• Subtask 19: 0 / 8
• Subtask 20: 0 / 8