oj.uz

Submission #975873

# Submission time Handle Problem Language Result Execution time Memory
975873 2024-05-06T01:45:13 Z gaga999 Cyberland (APIO23_cyberland) C++17
100 / 100
 1324 ms 13604 KB 
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef pair<llt, int> pli;
typedef complex<double> cd;
// const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}
typedef pair<double, int> pdl;

double solve(int n, int m, int k, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> ar)
{
    vector<pii> eg[n];
    for (int i = 0; i < m; i++)
        eg[x[i]].pb(c[i], y[i]), eg[y[i]].pb(c[i], x[i]);
    vector<double> ans(n, 1e18);
    vector<bool> vd(n, 0);
    {
        ans[0] = 0;
        queue<int> q;
        q.push(0), vd[0] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            if (u == H)
                continue;
            if (!ar[u])
                ans[u] = 0;
            for (pii v : eg[u])
                if (!vd[v.S])
                    q.push(v.S), vd[v.S] = 1;
        }
        if (!vd[H])
            return -1;
    }
    auto dij = [&]() -> void
    {
        priority_queue<pdl, vector<pdl>, greater<pdl>> pq;
        for (int i = 0; i < n; i++)
            if (ans[i] < 1e16)
                pq.emplace(ans[i], i);
        fill(iter(vd), 0);
        while (!pq.empty())
        {
            pdl tp = pq.top();
            pq.pop();
            if (vd[tp.S])
                continue;
            vd[tp.S] = 1;
            if (tp.S == H)
                continue;
            for (pii v : eg[tp.S])
                if (!vd[v.S] && ans[tp.S] + v.F < ans[v.S])
                    pq.emplace(ans[v.S] = ans[tp.S] + v.F, v.S);
        }
        for (int u = 0; u < n; u++)
        {
            if (ar[u] != 2 || !vd[u])
                continue;
            double mn = 1e18;
            for (pii v : eg[u])
                if (vd[v.S] && v.S != H)
                    tmin(mn, (ans[v.S] + v.F) / 2.0);
            pq.emplace(mn, u);
        }
        while (!pq.empty())
            tmin(ans[pq.top().S], pq.top().F), pq.pop();
    };
    for (int t = min(k, 80); t >= 0; t--)
        dij();
    return ans[H];
}

// signed main()
// {
//     int n, m, k, h;
//     rd(n, m, k, h);
//     vector<int> ar(n), x(m), y(m), c(m);
//     for (int i = 0; i < n; i++)
//         rd(ar[i]);
//     for (int i = 0; i < m; i++)
//         rd(x[i], y[i], c[i]);
//     cout << solve(n, m, k, h, x, y, c, ar) << '\n';
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 604 KB Correct.
2 Correct 32 ms 344 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 604 KB Correct.
2 Correct 126 ms 592 KB Correct.
3 Correct 121 ms 552 KB Correct.
4 Correct 132 ms 348 KB Correct.
5 Correct 131 ms 520 KB Correct.
6 Correct 176 ms 1868 KB Correct.
7 Correct 235 ms 1796 KB Correct.
8 Correct 108 ms 3232 KB Correct.
9 Correct 64 ms 544 KB Correct.
10 Correct 68 ms 596 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 564 KB Correct.
2 Correct 127 ms 564 KB Correct.
3 Correct 107 ms 592 KB Correct.
4 Correct 71 ms 344 KB Correct.
5 Correct 72 ms 344 KB Correct.
6 Correct 35 ms 1424 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 6420 KB Correct.
2 Correct 107 ms 592 KB Correct.
3 Correct 88 ms 580 KB Correct.
4 Correct 93 ms 348 KB Correct.
5 Correct 59 ms 496 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 596 KB Correct.
2 Correct 63 ms 580 KB Correct.
3 Correct 62 ms 604 KB Correct.
4 Correct 105 ms 1600 KB Correct.
5 Correct 35 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 596 KB Correct.
2 Correct 43 ms 604 KB Correct.
3 Correct 32 ms 7804 KB Correct.
4 Correct 54 ms 1408 KB Correct.
5 Correct 41 ms 348 KB Correct.
6 Correct 51 ms 592 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 588 KB Correct.
2 Correct 13 ms 604 KB Correct.
3 Correct 504 ms 13432 KB Correct.
4 Correct 383 ms 3436 KB Correct.
5 Correct 298 ms 7720 KB Correct.
6 Correct 112 ms 5116 KB Correct.
7 Correct 374 ms 3640 KB Correct.
8 Correct 290 ms 852 KB Correct.
9 Correct 67 ms 600 KB Correct.
10 Correct 61 ms 596 KB Correct.
11 Correct 231 ms 596 KB Correct.
12 Correct 80 ms 804 KB Correct.
13 Correct 76 ms 592 KB Correct.
14 Correct 307 ms 6816 KB Correct.
15 Correct 307 ms 2116 KB Correct.
16 Correct 68 ms 596 KB Correct.
17 Correct 91 ms 600 KB Correct.
18 Correct 75 ms 588 KB Correct.
19 Correct 279 ms 600 KB Correct.
20 Correct 4 ms 544 KB Correct.
21 Correct 5 ms 348 KB Correct.
22 Correct 9 ms 860 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 592 KB Correct.
2 Correct 30 ms 600 KB Correct.
3 Correct 1187 ms 13604 KB Correct.
4 Correct 400 ms 3432 KB Correct.
5 Correct 722 ms 9692 KB Correct.
6 Correct 244 ms 6928 KB Correct.
7 Correct 595 ms 7964 KB Correct.
8 Correct 344 ms 2852 KB Correct.
9 Correct 126 ms 1360 KB Correct.
10 Correct 118 ms 1456 KB Correct.
11 Correct 233 ms 1588 KB Correct.
12 Correct 151 ms 1620 KB Correct.
13 Correct 158 ms 1756 KB Correct.
14 Correct 1099 ms 8584 KB Correct.
15 Correct 1324 ms 9408 KB Correct.
16 Correct 596 ms 4764 KB Correct.
17 Correct 399 ms 2896 KB Correct.
18 Correct 122 ms 1620 KB Correct.
19 Correct 189 ms 1444 KB Correct.
20 Correct 154 ms 1616 KB Correct.
21 Correct 589 ms 2320 KB Correct.
22 Correct 7 ms 348 KB Correct.
23 Correct 9 ms 596 KB Correct.
24 Correct 18 ms 1116 KB Correct.