oj.uz

Submission #381001

# Submission time Handle Problem Language Result Execution time Memory
381001 2021-03-24T07:27:14 Z alrad Drzava (COCI15_drzava) C++17
72 / 160
 1000 ms 10784 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 24 ms 2536 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 23 ms 2156 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Correct 16 ms 2288 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 24 ms 2536 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 30 ms 2664 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 581 ms 7916 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1094 ms 10784 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1087 ms 10728 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1086 ms 10344 KB Time limit exceeded

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1093 ms 10728 KB Time limit exceeded

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1082 ms 10564 KB Time limit exceeded

Subtask #15
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Execution timed out 1083 ms 10600 KB Time limit exceeded

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1088 ms 10508 KB Time limit exceeded

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1087 ms 10612 KB Time limit exceeded

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB Output is correct
2 Execution timed out 1089 ms 10676 KB Time limit exceeded

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1086 ms 10744 KB Time limit exceeded

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Execution timed out 1095 ms 10600 KB Time limit exceeded