oj.uz

Submission #982321

# Submission time Handle Problem Language Result Execution time Memory
982321 2024-05-14T06:34:12 Z Seb Cyberland (APIO23_cyberland) C++17
100 / 100
 2356 ms 24088 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using lld = double;
using pid = pair<int, double>;
using vpid = vector<pid>;
using vii = vector<int>;

#define pb push_back
#define MP make_pair
#define f first
#define s second

const double INFd = (double)1e15;

void dfs(int nodo, vector<vpid> &g, vii &arr, vector <double> &ans, vector <bool> &vis) {
    if (arr[nodo] == 0) ans[nodo] = 0;
    vis[nodo] = true;
    for (auto &it : g[nodo]) {
        if (vis[it.f]) continue;
        dfs(it.f, g, arr, ans, vis);
    }
    return;
}

void djks(int N, int H, vector<vpid> &g, vector <double> &ans, vector<bool> &VIS) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    bool vis[N + 1];
    for (int i = 0; i <= N; i++) vis[i] = false;
    vis[H] = true;

    for (int i = 0; i < N; i++)
        if (i != H && VIS[i]) pq.push(MP(ans[i], i));

    while (!pq.empty()) {
        while (!pq.empty() && vis[pq.top().s]) pq.pop();
        if (pq.empty()) break;
        auto p = pq.top();
        vis[p.s] = true;
        ans[p.s] = min(ans[p.s], p.f);

        for (auto &it : g[p.s]) {
            if (vis[it.f]) continue;
            pq.push(MP(it.s + p.f, it.f));
        }
    }
    return;
}

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> arr) {
    vector<vpid> g(N + 1);
    for (int i = 0; i < M; i++) {
        g[x[i]].pb(MP(y[i], c[i]));
        g[y[i]].pb(MP(x[i], c[i]));
    }
    vector <bool> vis(N + 1, false);
    vector <double> ans(N + 1, INFd);
    vector <double> aux(N + 1, INFd);
    vis[H] = true;
    dfs(0, g, arr, ans, vis);
    ans[0] = 0;

    K = min(K, 80);
    for (int i = 0; i < K; i++) {

        djks(N, H, g, ans, vis);

        aux = ans;
        for (int i = 0; i < N; i++)
            if (i != H && vis[i] && arr[i] == 2)
                for (auto &it : g[i])
                    if (it.f != H)
                        aux[i] = min(aux[i], (double)((it.s + ans[it.f])/2));
        for (int i = 0; i <= N; i++) ans[i] = min(ans[i], aux[i]);
    }
    djks(N, H, g, ans, vis);

    double ANS = INFd;
    for (auto &it : g[H])
            if (vis[it.f])
                ANS = min(ANS, (double)(it.s + ans[it.f]));

    if (ANS == INFd) ANS = -1;
    return ANS;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 348 KB Correct.
2 Correct 36 ms 580 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 848 KB Correct.
2 Correct 314 ms 852 KB Correct.
3 Correct 300 ms 604 KB Correct.
4 Correct 311 ms 608 KB Correct.
5 Correct 310 ms 884 KB Correct.
6 Correct 354 ms 2036 KB Correct.
7 Correct 475 ms 2008 KB Correct.
8 Correct 204 ms 3668 KB Correct.
9 Correct 110 ms 516 KB Correct.
10 Correct 110 ms 536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 604 KB Correct.
2 Correct 292 ms 848 KB Correct.
3 Correct 263 ms 604 KB Correct.
4 Correct 115 ms 516 KB Correct.
5 Correct 116 ms 516 KB Correct.
6 Correct 73 ms 1896 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9152 KB Correct.
2 Correct 168 ms 600 KB Correct.
3 Correct 144 ms 644 KB Correct.
4 Correct 154 ms 600 KB Correct.
5 Correct 78 ms 516 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 656 KB Correct.
2 Correct 181 ms 600 KB Correct.
3 Correct 197 ms 604 KB Correct.
4 Correct 262 ms 1884 KB Correct.
5 Correct 67 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 680 KB Correct.
2 Correct 150 ms 652 KB Correct.
3 Correct 38 ms 9820 KB Correct.
4 Correct 147 ms 1972 KB Correct.
5 Correct 77 ms 524 KB Correct.
6 Correct 170 ms 628 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 596 KB Correct.
2 Correct 35 ms 604 KB Correct.
3 Correct 798 ms 16656 KB Correct.
4 Correct 551 ms 3916 KB Correct.
5 Correct 655 ms 13028 KB Correct.
6 Correct 470 ms 10408 KB Correct.
7 Correct 538 ms 4316 KB Correct.
8 Correct 416 ms 932 KB Correct.
9 Correct 172 ms 612 KB Correct.
10 Correct 191 ms 604 KB Correct.
11 Correct 351 ms 604 KB Correct.
12 Correct 186 ms 596 KB Correct.
13 Correct 186 ms 652 KB Correct.
14 Correct 458 ms 8588 KB Correct.
15 Correct 452 ms 2492 KB Correct.
16 Correct 185 ms 836 KB Correct.
17 Correct 213 ms 604 KB Correct.
18 Correct 205 ms 624 KB Correct.
19 Correct 533 ms 604 KB Correct.
20 Correct 8 ms 492 KB Correct.
21 Correct 13 ms 344 KB Correct.
22 Correct 41 ms 1444 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 648 KB Correct.
2 Correct 77 ms 600 KB Correct.
3 Correct 1881 ms 24088 KB Correct.
4 Correct 629 ms 1608 KB Correct.
5 Correct 1697 ms 13268 KB Correct.
6 Correct 1206 ms 10708 KB Correct.
7 Correct 970 ms 8084 KB Correct.
8 Correct 535 ms 2564 KB Correct.
9 Correct 394 ms 1820 KB Correct.
10 Correct 388 ms 1364 KB Correct.
11 Correct 239 ms 1560 KB Correct.
12 Correct 436 ms 1452 KB Correct.
13 Correct 435 ms 1536 KB Correct.
14 Correct 2356 ms 11988 KB Correct.
15 Correct 2251 ms 10456 KB Correct.
16 Correct 907 ms 5216 KB Correct.
17 Correct 652 ms 2904 KB Correct.
18 Correct 427 ms 1608 KB Correct.
19 Correct 518 ms 1704 KB Correct.
20 Correct 473 ms 1620 KB Correct.
21 Correct 1321 ms 2792 KB Correct.
22 Correct 15 ms 348 KB Correct.
23 Correct 29 ms 632 KB Correct.
24 Correct 106 ms 1576 KB Correct.