oj.uz

Submission #1018575

# Submission time Handle Problem Language Result Execution time Memory
1018575 2024-07-10T07:01:39 Z caterpillow Drzava (COCI15_drzava) C++17
64 / 160
 96 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

struct DSU {
    vt<int> e;
    void init(int n) { e.resize(n, -1); }
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (e[x] < e[y]) swap(x, y);
        e[y] += e[x];
        e[x] = y;
        return true;
    }
};

/*

bsearch on D
we can do a bitmask knapsack to check in O(fast)

idk how to build the connected components fast

*/

using db = long double;
using pd = pair<db, db>;
using t3 = tuple<db, int, int>;

int n, k;
vt<int> v;
vt<pd> pts;
vt<t3> edges;

#define sq(x) ((x) * (x))
db dist(pd a, pd b) {
    return sqrtl(sq(a.f - b.f) + sq(a.s - b.s));
}

void process() {
    cin >> n >> k;
    v.resize(n);
    pts.resize(n);
    F0R (i, n) {
        db x, y; ll pop;
        cin >> x >> y >> pop;
        pts[i] = {x, y};
        v[i] = pop % k;
    }

    vt<t3> poss;
    F0R (i, n) {
        FOR (j, i + 1, n) {
            poss.pb({dist(pts[i], pts[j]), i, j});
        }
    }
    sort(all(poss));
    DSU dsu; 
    dsu.init(n);
    for (auto [w, u, v] : poss) {
        if (dsu.unite(u, v)) {
            edges.pb({w, u, v});
        }
    }
}

void add_weight(ll& dp, ll w) {
    dp |= dp << w;
    dp |= dp >> k;
}

bool check(db d) {
    DSU dsu;
    dsu.init(n);
    for (auto [w, u, v] : edges) {
        if (w > d) break;
        dsu.unite(u, v);
    }
    vt<ll> msks(n, 1);
    F0R (u, n) {
        int rep = dsu.find(u);
        add_weight(msks[rep], v[u]);
    }
    F0R (i, n) {
        if (1 & (msks[i] >> k)) return true;
    }
    return false;
} 

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    process();

    const db eps = 1e-6;
    db lo = 0, hi = 1e9;
    while (hi - lo > eps) {
        db m = (lo + hi) / 2;
        if (check(m)) hi = m;
        else lo = m;
    }
    cout << fixed << setprecision(3) << hi << endl;
}

Compilation message

drzava.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 74 ms 17240 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 70 ms 19024 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 29 ms 9420 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 72 ms 17544 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 96 ms 17604 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 26 ms 10120 KB Output is correct

Subtask #9
0 / 8.0

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

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 50 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 1 ms 348 KB Output is correct
2 Runtime error 56 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 0 ms 344 KB Output is correct
2 Runtime error 48 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

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

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 51 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 0 ms 348 KB Output is correct
2 Runtime error 50 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #16
0 / 8.0

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

Subtask #17
0 / 8.0

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

Subtask #18
0 / 8.0

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

Subtask #19
0 / 8.0

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

Subtask #20
0 / 8.0

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