oj.uz

Submission #1113946

# Submission time Handle Problem Language Result Execution time Memory
1113946 2024-11-17T21:44:31 Z lucascgar Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 106080 KB 
#include <bits/stdc++.h>

using namespace std;

/*

*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 1e5+10, MAXK = 30+15;
const long long BIG = 1e18+8;

const long double PRECISION = 1e-7;

vector<pair<int, long double>> e[MAXN];

long double ds[MAXN][MAXK];

bool r[MAXN];

void dfs(int x, int H){
    r[x] = 1;
    if (x==H) return;
    for (auto &[i,cst]:e[x]) if (!r[i]) dfs(i, H);
}

double solve(int n, int m, int k, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){

    for (int i=0;i<n;i++){
        e[i].clear();
        for (int j=0;j<=k;j++) ds[i][j]=BIG;
        r[i] = 0;
    }

    for (int i=0;i<m;i++){
        int a = x[i], b = y[i];
        e[a].emplace_back(b, c[i]);
        e[b].emplace_back(a,c[i]);
    }
    dfs(0, H);
    typedef tuple<long double, int, int> node;  // {dst, qntk, u}
    priority_queue<node, vector<node>, greater<>> q;
    for (int i=0;i<n;i++) if (!i || (r[i] && arr[i]==0)){
        ds[i][0] = 0;
        q.emplace(0, 0, i);
    }

    while (!q.empty()){
        auto [d, qk, u] = q.top();
        q.pop();
        if (ds[u][qk] != d) continue;

        if (u == H) continue;

        for (auto &[i, cs]:e[u]){
            long double nc = d+cs;
            // sem usar
            if (ds[i][qk]>nc){
                ds[i][qk] = nc;
                q.emplace(nc, qk, i);
            }

            // usando

            nc /= 2.00;
            if (qk<k && arr[i] == 2 && ds[i][qk+1]> nc){
                ds[i][qk+1] = nc;
                q.emplace(nc, qk+1, i);
            }
        }
    }
    long double ans = BIG;
    for (int i=0;i<=k;i++) ans = min(ans, ds[H][i]);
 
    // cerr << ds[1][4] << '\n';

    if (ans == BIG) return -1;
    return ans;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3408 KB Correct.
2 Correct 29 ms 3664 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5712 KB Correct.
2 Correct 31 ms 5712 KB Correct.
3 Correct 32 ms 5880 KB Correct.
4 Correct 31 ms 5712 KB Correct.
5 Correct 39 ms 5712 KB Correct.
6 Correct 29 ms 13136 KB Correct.
7 Correct 39 ms 13148 KB Correct.
8 Correct 22 ms 19536 KB Correct.
9 Correct 28 ms 3408 KB Correct.
10 Correct 28 ms 3408 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5712 KB Correct.
2 Correct 34 ms 6748 KB Correct.
3 Correct 35 ms 6736 KB Correct.
4 Correct 32 ms 4424 KB Correct.
5 Correct 31 ms 4452 KB Correct.
6 Correct 10 ms 11512 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 59312 KB Correct.
2 Correct 527 ms 7484 KB Correct.
3 Correct 456 ms 7340 KB Correct.
4 Correct 466 ms 7492 KB Correct.
5 Correct 405 ms 4460 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5968 KB Correct.
2 Correct 28 ms 5980 KB Correct.
3 Correct 28 ms 5968 KB Correct.
4 Correct 28 ms 13988 KB Correct.
5 Correct 24 ms 3576 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5968 KB Correct.
2 Correct 25 ms 6736 KB Correct.
3 Correct 79 ms 67912 KB Correct.
4 Correct 22 ms 12016 KB Correct.
5 Correct 27 ms 4432 KB Correct.
6 Correct 27 ms 6972 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 7680 KB Correct.
2 Correct 69 ms 9396 KB Correct.
3 Correct 1149 ms 88556 KB Correct.
4 Correct 900 ms 25644 KB Correct.
5 Correct 1989 ms 106080 KB Correct.
6 Correct 906 ms 88456 KB Correct.
7 Correct 847 ms 26224 KB Correct.
8 Correct 835 ms 10508 KB Correct.
9 Correct 450 ms 10412 KB Correct.
10 Correct 451 ms 8736 KB Correct.
11 Correct 829 ms 7996 KB Correct.
12 Correct 485 ms 9132 KB Correct.
13 Correct 521 ms 8696 KB Correct.
14 Correct 711 ms 47892 KB Correct.
15 Correct 838 ms 19152 KB Correct.
16 Correct 445 ms 8844 KB Correct.
17 Correct 545 ms 8556 KB Correct.
18 Correct 533 ms 8584 KB Correct.
19 Correct 1279 ms 9572 KB Correct.
20 Correct 42 ms 4116 KB Correct.
21 Correct 36 ms 6740 KB Correct.
22 Correct 59 ms 12992 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 17808 KB Time limit exceeded
2 Halted 0 ms 0 KB -