oj.uz

Submission #253804

# Submission time Handle Problem Language Result Execution time Memory
253804 2020-07-28T17:25:00 Z Vimmer Drzava (COCI15_drzava) C++14
32 / 160
 1000 ms 9904 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 50050
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 5> a5;

//typedef tree <ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int n, k, kol[N], pr[N];

ld x[N], y[N];

multiset <int> se[N];

void make(int x) {pr[x] = x; se[x].clear(); se[x].insert(kol[x]);}

int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}

void link(int a, int b)
{
    if (sz(se[a]) < sz(se[b])) swap(a, b);

    pr[b] = a;

    for (auto it : se[b]) se[a].insert(it);
}

ld dist(int a, int b) {return sqrt(pow(x[a] - x[b], 2) + pow(y[a] - y[b], 2));}

bool can(ld x)
{
    for (int i = 0; i < n; i++) make(i);

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            int a = fnd(i), b = fnd(j);

            if (a == b) continue;

            if (x - dist(i, j) >= 0.00000001)
                link(a, b);
        }

    set <int> st; st.clear();

    for (int i = 0; i < n; i++) st.insert(fnd(i));

    for (auto it : st)
    {
        vector <int> vals; vals.clear();

        for (auto itr : se[it]) vals.pb(itr);

        bool f[sz(vals) + 1][k];

        memset(f, 0, sizeof(f));

        f[1][vals[0]] = 1;

        for (int i = 1; i < sz(vals); i++)
          for (int j = 0; j < k; j++)
            if (f[i][j] || j == 0)
            {
                f[i + 1][j] = 1;

                int nval = (j + vals[i]) % k;

                if (nval == 0) return 1;

                f[i + 1][nval] = 1;
            }
    }

    return 0;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++) {cin >> x[i] >> y[i] >> kol[i]; kol[i] %= k;}

    ld l = 0, r = 100000000;

    while (r - l >= 0.0000001)
    {
        ld md = (r + l) * 0.5;

        if (can(md)) r = md; else l = md;
    }

    cout << setprecision(3) << fixed;

    cout << l << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Execution timed out 1078 ms 3008 KB Time limit exceeded

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Execution timed out 1058 ms 2816 KB Time limit exceeded

Subtask #5
8.0 / 8.0

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

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Execution timed out 1080 ms 2932 KB Time limit exceeded

Subtask #7
0 / 8.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 568 ms 2872 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Execution timed out 1085 ms 6264 KB Time limit exceeded

Subtask #10
0 / 8.0

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

Subtask #11
0 / 8.0

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

Subtask #12
0 / 8.0

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

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Execution timed out 1085 ms 9852 KB Time limit exceeded

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Execution timed out 1070 ms 9848 KB Time limit exceeded

Subtask #15
0 / 8.0

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

Subtask #16
0 / 8.0

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

Subtask #17
0 / 8.0

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

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Execution timed out 1081 ms 9848 KB Time limit exceeded

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Execution timed out 1090 ms 9848 KB Time limit exceeded

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Execution timed out 1068 ms 9848 KB Time limit exceeded