oj.uz

Submission #1056452

# Submission time Handle Problem Language Result Execution time Memory
1056452 2024-08-13T09:28:54 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 128064 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const long long INF = 1e18;
const int MAXK = 70;
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 50268 KB Correct.
2 Correct 21 ms 50268 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 50268 KB Correct.
2 Correct 27 ms 50316 KB Correct.
3 Correct 26 ms 50268 KB Correct.
4 Correct 28 ms 50268 KB Correct.
5 Correct 28 ms 50520 KB Correct.
6 Correct 24 ms 51180 KB Correct.
7 Correct 31 ms 51036 KB Correct.
8 Correct 20 ms 52060 KB Correct.
9 Correct 25 ms 50228 KB Correct.
10 Correct 25 ms 50012 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50268 KB Correct.
2 Correct 29 ms 50296 KB Correct.
3 Correct 27 ms 50268 KB Correct.
4 Correct 27 ms 50008 KB Correct.
5 Correct 27 ms 50012 KB Correct.
6 Correct 9 ms 50780 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 56408 KB Correct.
2 Correct 854 ms 50512 KB Correct.
3 Correct 671 ms 50268 KB Correct.
4 Correct 730 ms 50312 KB Correct.
5 Correct 603 ms 50264 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 50268 KB Correct.
2 Correct 26 ms 50268 KB Correct.
3 Correct 25 ms 50268 KB Correct.
4 Correct 25 ms 51232 KB Correct.
5 Correct 23 ms 50012 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50384 KB Correct.
2 Correct 23 ms 50268 KB Correct.
3 Correct 37 ms 57684 KB Correct.
4 Correct 19 ms 51036 KB Correct.
5 Correct 25 ms 50012 KB Correct.
6 Correct 24 ms 50268 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 53236 KB Correct.
2 Correct 79 ms 53348 KB Correct.
3 Correct 2013 ms 40856 KB Correct.
4 Correct 1875 ms 44216 KB Correct.
5 Correct 1758 ms 124680 KB Correct.
6 Correct 531 ms 88876 KB Correct.
7 Correct 1798 ms 51240 KB Correct.
8 Correct 1786 ms 51088 KB Correct.
9 Correct 568 ms 52216 KB Correct.
10 Correct 601 ms 53280 KB Correct.
11 Correct 1718 ms 51060 KB Correct.
12 Correct 623 ms 52096 KB Correct.
13 Correct 622 ms 53288 KB Correct.
14 Correct 1366 ms 56196 KB Correct.
15 Correct 1984 ms 52592 KB Correct.
16 Correct 550 ms 52184 KB Correct.
17 Correct 750 ms 52092 KB Correct.
18 Correct 720 ms 52152 KB Correct.
19 Correct 2267 ms 53196 KB Correct.
20 Correct 43 ms 50428 KB Correct.
21 Correct 51 ms 51472 KB Correct.
22 Correct 51 ms 55244 KB Correct.

Subtask #8
0.0 / 3.0

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