oj.uz

Submission #1056446

# Submission time Handle Problem Language Result Execution time Memory
1056446 2024-08-13T09:27:52 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 2281 ms 123896 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const long long INF = 1e18;
const int MAXK = 60;
vector<pair<int,int>> con[100005];
vector<int> tip;
ld dist[MAXK+1][100005];
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) {
    K = min(K, MAXK);
    for(int i=0;i<N;i++)
    {
        con[i].clear();
    }
    tip = arr;
    for(int i=0;i<M;i++)
    {
        con[x[i]].push_back({y[i],c[i]});
        con[y[i]].push_back({x[i],c[i]});
    }
    for(int nr=0;nr<=K;nr++)
        for(int i=0;i<N;i++)
            dist[nr][i]=INF;
    priority_queue<pair<ld,pair<int,int>>> pq;
    dist[0][0]=0;
    pq.push({0,{0,0}});
    while(!pq.empty())
    {
        ld cdist = -pq.top().first;
        int nod = pq.top().second.second;
        int cnt = pq.top().second.first;
        pq.pop();
        if(cdist!=dist[cnt][nod] || nod==H)
            continue;
        for(auto [adj,c]:con[nod])
        {
            if(tip[adj]==0)
            {
                if(dist[cnt][adj]>0)
                {
                    dist[cnt][adj]=0;
                    pq.push({0,{cnt,adj}});
                }
            }
            else if(tip[adj]==2)
            {
                if(dist[cnt][adj] > cdist + c)
                {
                    dist[cnt][adj] = cdist + c;
                    pq.push({-dist[cnt][adj],{cnt,adj}});
                }
                if(cnt+1<=K && dist[cnt+1][adj] > (cdist + (ld)c)/2)
                {
                    dist[cnt+1][adj] = (cdist + (ld)c)/2;
                    pq.push({-dist[cnt+1][adj],{cnt+1,adj}});
                }
            }
            else
            {
                if(dist[cnt][adj] > cdist + c)
                {
                    dist[cnt][adj] = cdist + c;
                    pq.push({-dist[cnt][adj],{cnt,adj}});
                }
            }
        }
    }
    ld mnm=INF;
    for(int cnt=0;cnt<=K;cnt++)
        mnm = min(mnm, dist[cnt][H]);
    if(mnm==INF)
        return -1;
    else
        return mnm;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51032 KB Correct.
2 Correct 22 ms 51036 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51032 KB Correct.
2 Correct 28 ms 51036 KB Correct.
3 Correct 26 ms 51036 KB Correct.
4 Correct 27 ms 51036 KB Correct.
5 Correct 41 ms 51064 KB Correct.
6 Correct 37 ms 51792 KB Correct.
7 Correct 32 ms 51700 KB Correct.
8 Correct 16 ms 52568 KB Correct.
9 Correct 40 ms 50984 KB Correct.
10 Correct 38 ms 50980 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 51036 KB Correct.
2 Correct 30 ms 51036 KB Correct.
3 Correct 31 ms 51052 KB Correct.
4 Correct 30 ms 50976 KB Correct.
5 Correct 34 ms 50972 KB Correct.
6 Correct 11 ms 51548 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 57068 KB Correct.
2 Correct 810 ms 51020 KB Correct.
3 Correct 682 ms 51032 KB Correct.
4 Correct 743 ms 51248 KB Correct.
5 Correct 634 ms 51032 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51032 KB Correct.
2 Correct 26 ms 51044 KB Correct.
3 Correct 25 ms 51036 KB Correct.
4 Correct 24 ms 51976 KB Correct.
5 Correct 23 ms 50780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51036 KB Correct.
2 Correct 23 ms 51072 KB Correct.
3 Correct 44 ms 58540 KB Correct.
4 Correct 19 ms 51908 KB Correct.
5 Correct 27 ms 50776 KB Correct.
6 Correct 25 ms 51036 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 54216 KB Correct.
2 Correct 83 ms 54036 KB Correct.
3 Correct 2009 ms 41540 KB Correct.
4 Correct 1876 ms 44984 KB Correct.
5 Correct 1755 ms 123896 KB Correct.
6 Correct 577 ms 89256 KB Correct.
7 Correct 1781 ms 51936 KB Correct.
8 Correct 1758 ms 51944 KB Correct.
9 Correct 566 ms 53088 KB Correct.
10 Correct 598 ms 54068 KB Correct.
11 Correct 1749 ms 51712 KB Correct.
12 Correct 616 ms 52864 KB Correct.
13 Correct 651 ms 54012 KB Correct.
14 Correct 1456 ms 57192 KB Correct.
15 Correct 1967 ms 53512 KB Correct.
16 Correct 560 ms 52788 KB Correct.
17 Correct 732 ms 52876 KB Correct.
18 Correct 708 ms 52940 KB Correct.
19 Correct 2177 ms 53936 KB Correct.
20 Correct 42 ms 51200 KB Correct.
21 Correct 51 ms 52240 KB Correct.
22 Correct 61 ms 56780 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2281 ms 106592 KB Correct.
2 Correct 246 ms 105396 KB Correct.
3 Incorrect 763 ms 104784 KB Wrong Answer.
4 Halted 0 ms 0 KB -