oj.uz

Submission #1056440

# Submission time Handle Problem Language Result Execution time Memory
1056440 2024-08-13T09:26:56 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 2332 ms 124420 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const long long INF = 1e18;
const int MAXK = 30;
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 33 ms 51284 KB Correct.
2 Correct 22 ms 51544 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51292 KB Correct.
2 Correct 28 ms 51292 KB Correct.
3 Correct 29 ms 51288 KB Correct.
4 Correct 27 ms 51292 KB Correct.
5 Correct 28 ms 51312 KB Correct.
6 Correct 24 ms 52100 KB Correct.
7 Correct 34 ms 51900 KB Correct.
8 Correct 16 ms 52712 KB Correct.
9 Correct 32 ms 51032 KB Correct.
10 Correct 29 ms 51036 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51292 KB Correct.
2 Correct 30 ms 52056 KB Correct.
3 Correct 29 ms 52224 KB Correct.
4 Correct 29 ms 52060 KB Correct.
5 Correct 27 ms 51960 KB Correct.
6 Correct 9 ms 52060 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 55228 KB Correct.
2 Correct 800 ms 52372 KB Correct.
3 Correct 701 ms 52272 KB Correct.
4 Correct 769 ms 52308 KB Correct.
5 Correct 600 ms 52188 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51292 KB Correct.
2 Correct 29 ms 51344 KB Correct.
3 Correct 25 ms 51316 KB Correct.
4 Correct 24 ms 52192 KB Correct.
5 Correct 28 ms 51212 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51292 KB Correct.
2 Correct 24 ms 52232 KB Correct.
3 Correct 39 ms 58460 KB Correct.
4 Correct 22 ms 52732 KB Correct.
5 Correct 28 ms 52052 KB Correct.
6 Correct 27 ms 52308 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 54360 KB Correct.
2 Correct 79 ms 54512 KB Correct.
3 Correct 2094 ms 44048 KB Correct.
4 Correct 1956 ms 47400 KB Correct.
5 Correct 1696 ms 124420 KB Correct.
6 Correct 542 ms 90280 KB Correct.
7 Correct 1800 ms 54324 KB Correct.
8 Correct 1839 ms 53852 KB Correct.
9 Correct 568 ms 54132 KB Correct.
10 Correct 600 ms 55344 KB Correct.
11 Correct 1741 ms 53592 KB Correct.
12 Correct 616 ms 54160 KB Correct.
13 Correct 602 ms 55356 KB Correct.
14 Correct 1369 ms 58492 KB Correct.
15 Correct 2036 ms 55664 KB Correct.
16 Correct 593 ms 54236 KB Correct.
17 Correct 761 ms 54112 KB Correct.
18 Correct 739 ms 54192 KB Correct.
19 Correct 2332 ms 56268 KB Correct.
20 Correct 45 ms 51488 KB Correct.
21 Correct 59 ms 52376 KB Correct.
22 Correct 55 ms 57472 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 54296 KB Correct.
2 Correct 88 ms 54412 KB Correct.
3 Incorrect 442 ms 60496 KB Wrong Answer.
4 Halted 0 ms 0 KB -