oj.uz

Submission #156449

# Submission time Handle Problem Language Result Execution time Memory
156449 2019-10-05T17:05:24 Z ionanghelina Drzava (COCI15_drzava) C++14
160 / 160
 150 ms 13596 KB 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>

using namespace std;
typedef long long llint;

const int MAXN = 50005;
const int MAXK = 31;

int n, k;
int x[MAXN], y[MAXN], c[MAXN];

bool cmp (int i, int j) {
  if (x[i] != x[j]) return x[i] < x[j];
  return y[i] < y[j];
}

struct edge{
  int x, y;
  llint d;
  edge (int x, int y, llint d) : x(x), y(y), d(d) {}
};

bool operator < (const edge &A, const edge &B) {
  return A.d < B.d;
}

inline llint sqr (llint x) { return x*x; }
inline llint distx (int i, int j) { return sqr(x[i] - x[j]); }
inline llint disty (int i, int j) { return sqr(y[i] - y[j]); }
inline llint dist (int i, int j) { return distx(i, j) + disty(i, j); }

vector <edge> E;

struct cmp_set {
  bool operator () (const int i, const int j) {
    if (y[i] != y[j]) return y[i] < y[j];
    return i < j;
  }
};

struct cmp_nth {
  int x;
  cmp_nth (int x) : x(x) {}
  bool operator () (const int i, const int j) {
    return dist(x, i) < dist(x, j);
  }
};

int dad[MAXN];
vector <int> comp[MAXN];
bool value[MAXN][MAXK];

inline int fastmod (int x) { return x < 0 ? x + k : x; }

void update (int x, int v) {
  int tmp[MAXK];
  for (int i = 0; i < k; ++i)
    if (value[x][i] || v == i || value[x][fastmod(i - v)]) tmp[i] = 1;
    else tmp[i] = 0;

  for (int i = 0; i < k; ++i)
    value[x][i] = tmp[i];
}

void merge (int x, int y) {
  x = dad[x]; y = dad[y];
  if (comp[x].size() > comp[y].size()) swap(x, y);
  for (auto v: comp[x]) {
    dad[v] = y;
    comp[y].push_back(x);
    update(y, c[v]);
  }

  comp[x].clear();
}


int main (void){
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &c[i]);
  for (int i = 0; i < n; ++i) c[i] %= k;

  vector <int> V;
  for (int i = 0; i < n; ++i) V.push_back(i);

  sort(V.begin(), V.end(), cmp);

  llint best = 1LL << 60LL;
  int last = 0;
  set <int, cmp_set> S;
  for (int i = 0; i < V.size(); ++i) {
    int curr = V[i];
    while (distx(V[last], curr) > best) S.erase(V[last++]);

    int d = sqrt(best);
    y[n] = y[curr] - d;
    auto it = S.lower_bound(n);
    vector <int> close;
    while (it != S.end() && y[curr] + d >= y[*it]){
      llint dd = dist(*it, curr);
      if (dd <= best) {
	close.push_back(*it);
	E.push_back(edge(*it, curr, dd));
      }
      ++it;
    }
    
    if (close.size() >= k) {
      nth_element(close.begin(), close.begin() + k-1, close.begin(), cmp_nth(curr));
      best = dist(close[k - 1], curr);
    }

    S.insert(V[i]);
  }

  for (int i = 0; i < n; ++i) {
    comp[i].push_back(i);
    dad[i] = i;
    value[i][c[i]] = 1;
  }

  sort(E.begin(), E.end());
  for (int i = 0; i < E.size(); ++i) {
    edge e = E[i];
    if (dad[e.x] == dad[e.y]) continue;
    merge(e.x, e.y);
    if (value[dad[e.x]][0]) {
      printf("%.3lf\n", sqrt(e.d));
      return 0;
    }
  }

  return 0;
}

Compilation message

drzava.cpp: In function 'int main()':
drzava.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < V.size(); ++i) {
                   ~~^~~~~~~~~~
drzava.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (close.size() >= k) {
         ~~~~~~~~~~~~~^~~~
drzava.cpp:128:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < E.size(); ++i) {
                   ~~^~~~~~~~~~
drzava.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~
drzava.cpp:85:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &c[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1572 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1784 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1784 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1700 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 25 ms 3320 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 150 ms 13596 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 146 ms 13048 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 45 ms 5236 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 132 ms 11588 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 143 ms 12760 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 65 ms 6488 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1548 KB Output is correct
2 Correct 78 ms 7644 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 92 ms 9524 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 99 ms 10612 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 70 ms 6908 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 71 ms 7088 KB Output is correct