oj.uz

Submission #1088036

# Submission time Handle Problem Language Result Execution time Memory
1088036 2024-09-13T18:16:07 Z nguyen31hoang08minh2003 Drzava (COCI15_drzava) C++14
72 / 160
 1000 ms 65536 KB 
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

constexpr int MAX_N = 50'004, MAX_K = 31;
const double EPSILON = 1E-9;

bool checkSmaller(const double l, const double r) {
    return l + EPSILON < r;
}

bool checkEqual(const double l, const double r) {
    return fabs(r - l) <= EPSILON;
}

bool checkSmallerOrEqual(const double l, const double r) {
    return checkEqual(l, r) || checkSmaller(l, r);
}

bool visited[MAX_N], possible[MAX_K], newlyPossible[MAX_K];
int N, K, x[MAX_N], y[MAX_N], k[MAX_N];
vi vx, vy, rows[MAX_N], graph[MAX_N];
signed nx, ny, bound, before[MAX_N];
deque<int> columns[MAX_N];
double upperBound;

double calculateSquare(const double t) {
    return t * t;
}

double calculateDistance(const int u, const int v) {
    return sqrt(calculateSquare(vx[x[u]] - vx[x[v]]) + calculateSquare(vy[y[u]] - vy[y[v]]));
}

template<class T>
class SegmentTree {
private:

    int length;
    std::vector<T> total;

    void modify(const int q, const T value, const int i, const int l, const int r) {
        if (q < l || r < q)
            return;
        if (l == r) {
            total[i] = value;
            return;
        }
        const int m = l + r >> 1;
        modify(q, value, i << 1, l, m);
        modify(q, value, i << 1 | 1, m + 1, r);
        total[i] = total[i << 1] + total[i << 1 | 1];
    }

    void update(const int q, const T value, const int i, const int l, const int r) {
        if (q < l || r < q)
            return;
        total[i] += value;
        if (l == r)
            return;
        const int m = l + r >> 1;
        update(q, value, i << 1, l, m);
        update(q, value, i << 1 | 1, m + 1, r);
    }

    T query(const int ql, const int qr, const int i, const int l, const int r) const {
        if (qr < l || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return total[i];
        const int m = l + r >> 1;
        return query(ql, qr, i << 1, l, m) + query(ql, qr, i << 1 | 1, m + 1, r);
    }

    void build(const int i, const int l, const int r) {
        total[i] = 0;
        if (l == r)
            return;
        const int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

    void connect(const int ql, const int qr, const int u, const int i, const int l, const int r) const {
        if (qr < l || r < ql || total[i] == 0)
            return;
        if (l == r) {
            for (const int &v : columns[r]) {
                if (u == v || (x[u] == x[v] && y[v] < y[u]))
                    continue;
                if (checkSmallerOrEqual(calculateDistance(u, v), upperBound)) {
                    graph[u].pb(v);
                    graph[v].pb(u);
                }
            }
            return;
        }
        const int m = l + r >> 1;
        connect(ql, qr, u, i << 1, l, m);
        connect(ql, qr, u, i << 1 | 1, m + 1, r);
    }

public:

    SegmentTree(): length(0) {};
    SegmentTree(const int n): length(n), total(n + 5 << 2) {};

    void resize(int m) {
        length = m;
        m = length + 5 << 2;
        total.resize(m);
//        reload();
    }

    void reload() {
        std::fill(total.begin(), total.end(), 0);
    }

    void modify(const int q, const T value) {
        modify(q, value, 1, 0, length - 1);
    }

    void update(const int q, const T value) {
        update(q, value, 1, 0, length - 1);
    }

    T query(const int ql, const int qr) const {
        return query(ql, qr, 1, 0, length - 1);
    }

    void connect(const int ql, const int qr, const int id) const {
        connect(ql, qr, id, 1, 0, length - 1);
    }

    void build() {
        build(1, 0, length - 1);
    }

    T top() const {
        return total[1];
    }

    int getLength() const {
        return this -> length;
    }

    virtual ~SegmentTree() {}

};

SegmentTree<int> segmentTree;

int getSubtraction(int x, const int y) {
    if ((x -= y) < 0)
        x += K;
    return x;
}

void dfs(const int u) {
    visited[u] = true;

    fore(t, 0, K)
        newlyPossible[t] = possible[t] || possible[getSubtraction(t, k[u])];

    fore(t, 0, K)
        possible[t] = newlyPossible[t];

    possible[k[u]] = true;

    for (const int &v : graph[u]) {
        if (visited[v])
            continue;
        dfs(v);
    }
}

bool check(const double limit) {

    upperBound = limit;

    fore(i, 0, N) {
        graph[i].clear();
        visited[i] = false;
    }

    for (int g = 0, j = 0; j < nx; ++j) {
        columns[j].clear();
        for (; checkSmaller(limit, vx[j] - vx[g]); ++g);
        before[j] = g;
    }

    segmentTree.reload();

    for (int l = 0, i = 0, r = 0; i < ny; ++i) {

        for (; r < ny && checkSmallerOrEqual(vy[r] - vy[i], limit); ++r)
            for (const int &z : rows[r]) {
                columns[x[z]].push_back(z);
                segmentTree.modify(x[z], columns[x[z]].size());
            }

        for (; checkSmaller(limit, vy[i] - vy[l]); ++l)
            for (const int &z : rows[l]) {
                columns[x[z]].pop_front();
                segmentTree.modify(x[z], columns[x[z]].size());
            }

        for (const int &z : rows[i]) {
            if (segmentTree.query(before[x[z]], x[z]) > bound)
                return true;
            segmentTree.connect(before[x[z]], x[z], z);
        }
    }

    fore(u, 0, N) {
        if (visited[u])
            continue;
        fore(k, 0, K)
            possible[k] = false;
        dfs(u);
        if (possible[0])
            return true;
    }

    return false;
}

signed main() {

    double low = 0, middle, high = 2E9;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cout.precision(3);
    cout.setf(ios::fixed, ios::floatfield);

    cin >> N >> K;

    fore(i, 0, N) {
        cin >> x[i] >> y[i] >> k[i];
        vx.pb(x[i]);
        vy.pb(y[i]);
        k[i] %= K;
    }

    sort(all(vx));
    sort(all(vy));
    vx.erase(unique(all(vx)), vx.end());
    vy.erase(unique(all(vy)), vy.end());
    nx = vx.size();
    ny = vy.size();
    segmentTree.resize(nx);

    fore(i, 0, N) {
        x[i] = lower_bound(all(vx), x[i]) - vx.begin();
        y[i] = lower_bound(all(vy), y[i]) - vy.begin();
        rows[y[i]].pb(i);
    }

    bound = 8 * K;

    for (; low + 1E-6 < high;) {
        middle = (low + high) / 2;
        if (check(middle))
            high = middle;
        else
            low = middle;
    }

    cout << high << '\n';

    return 0;
}

Compilation message

drzava.cpp: In instantiation of 'void SegmentTree<T>::resize(int) [with T = int]':
drzava.cpp:302:26:   required from here
drzava.cpp:157:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  157 |         m = length + 5 << 2;
      |             ~~~~~~~^~~
drzava.cpp: In instantiation of 'void SegmentTree<T>::modify(int, T, int, int, int) [with T = int]':
drzava.cpp:167:15:   required from 'void SegmentTree<T>::modify(int, T) [with T = int]'
drzava.cpp:246:62:   required from here
drzava.cpp:96:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         const int m = l + r >> 1;
      |                       ~~^~~
drzava.cpp: In instantiation of 'T SegmentTree<T>::query(int, int, int, int, int) const [with T = int]':
drzava.cpp:175:21:   required from 'T SegmentTree<T>::query(int, int) const [with T = int]'
drzava.cpp:256:53:   required from here
drzava.cpp:118:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         const int m = l + r >> 1;
      |                       ~~^~~
drzava.cpp: In instantiation of 'void SegmentTree<T>::connect(int, int, int, int, int, int) const [with T = int]':
drzava.cpp:179:16:   required from 'void SegmentTree<T>::connect(int, int, int) const [with T = int]'
drzava.cpp:258:54:   required from here
drzava.cpp:145:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |         const int m = l + r >> 1;
      |                       ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36444 KB Output is correct
2 Correct 15 ms 36360 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36444 KB Output is correct
2 Correct 19 ms 36696 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36440 KB Output is correct
2 Correct 27 ms 37212 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36440 KB Output is correct
2 Correct 27 ms 36700 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36444 KB Output is correct
2 Correct 23 ms 36700 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36440 KB Output is correct
2 Correct 27 ms 37124 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36440 KB Output is correct
2 Correct 30 ms 37212 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36440 KB Output is correct
2 Correct 26 ms 36956 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36440 KB Output is correct
2 Correct 523 ms 42824 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36440 KB Output is correct
2 Runtime error 597 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36444 KB Output is correct
2 Runtime error 610 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36440 KB Output is correct
2 Execution timed out 1031 ms 59136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36444 KB Output is correct
2 Execution timed out 1077 ms 63048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36324 KB Output is correct
2 Runtime error 614 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #15
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36444 KB Output is correct
2 Execution timed out 1075 ms 45476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36440 KB Output is correct
2 Execution timed out 1085 ms 51172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36444 KB Output is correct
2 Execution timed out 1057 ms 60432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36444 KB Output is correct
2 Execution timed out 1039 ms 60468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36440 KB Output is correct
2 Execution timed out 1081 ms 48056 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36444 KB Output is correct
2 Execution timed out 1052 ms 47712 KB Time limit exceeded
3 Halted 0 ms 0 KB -