oj.uz

Submission #1056474

# Submission time Handle Problem Language Result Execution time Memory
1056474 2024-08-13T09:36:47 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 1929 ms 126112 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const long long INF = 1e18;
const int MAXK = 64;
vector<pair<int,int>> con[100005];
vector<int> tip;
ld dist[MAXK+1][100005];

bool visited[100005];
void dfs(int nod, int H)
{
    visited[nod]=1;
    for(auto [adj,c]:con[nod])
        if(!visited[adj] && adj!=H)
            dfs(adj,H);
}

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();
        visited[i]=0;
    }
    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]});
    }
    dfs(0,H);
    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;
    for(int i=0;i<N;i++)
    {
        if(i==0 || (visited[i] && tip[i]==0))
        {
            pq.push({0,{0,i}});
            dist[0][i]=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 51292 KB Correct.
2 Correct 26 ms 51256 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51292 KB Correct.
2 Correct 33 ms 51292 KB Correct.
3 Correct 29 ms 51268 KB Correct.
4 Correct 28 ms 51276 KB Correct.
5 Correct 32 ms 51284 KB Correct.
6 Correct 26 ms 51880 KB Correct.
7 Correct 35 ms 51804 KB Correct.
8 Correct 18 ms 54804 KB Correct.
9 Correct 27 ms 51196 KB Correct.
10 Correct 29 ms 51200 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 51300 KB Correct.
2 Correct 31 ms 51292 KB Correct.
3 Correct 29 ms 51288 KB Correct.
4 Correct 27 ms 51152 KB Correct.
5 Correct 29 ms 51204 KB Correct.
6 Correct 10 ms 52056 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 65964 KB Correct.
2 Correct 577 ms 51992 KB Correct.
3 Correct 497 ms 52060 KB Correct.
4 Correct 542 ms 52140 KB Correct.
5 Correct 436 ms 51284 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51292 KB Correct.
2 Correct 27 ms 51292 KB Correct.
3 Correct 27 ms 51292 KB Correct.
4 Correct 27 ms 52148 KB Correct.
5 Correct 34 ms 51184 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51292 KB Correct.
2 Correct 27 ms 51292 KB Correct.
3 Correct 38 ms 58788 KB Correct.
4 Correct 19 ms 52060 KB Correct.
5 Correct 25 ms 51080 KB Correct.
6 Correct 28 ms 51292 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 52956 KB Correct.
2 Correct 75 ms 55560 KB Correct.
3 Correct 1093 ms 45256 KB Correct.
4 Correct 1033 ms 46604 KB Correct.
5 Correct 1598 ms 126112 KB Correct.
6 Correct 533 ms 89260 KB Correct.
7 Correct 1027 ms 51544 KB Correct.
8 Correct 1108 ms 52288 KB Correct.
9 Correct 459 ms 53044 KB Correct.
10 Correct 479 ms 53348 KB Correct.
11 Correct 1112 ms 51856 KB Correct.
12 Correct 496 ms 52908 KB Correct.
13 Correct 502 ms 53076 KB Correct.
14 Correct 752 ms 57768 KB Correct.
15 Correct 1044 ms 53808 KB Correct.
16 Correct 485 ms 53076 KB Correct.
17 Correct 546 ms 52840 KB Correct.
18 Correct 530 ms 52984 KB Correct.
19 Correct 1444 ms 53144 KB Correct.
20 Correct 41 ms 51444 KB Correct.
21 Correct 41 ms 52096 KB Correct.
22 Correct 51 ms 56256 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1929 ms 112268 KB Correct.
2 Correct 270 ms 112188 KB Correct.
3 Incorrect 819 ms 113032 KB Wrong Answer.
4 Halted 0 ms 0 KB -