oj.uz

Submission #1056490

# Submission time Handle Problem Language Result Execution time Memory
1056490 2024-08-13T09:43:19 Z alexdd Cyberland (APIO23_cyberland) C++17
100 / 100
 2956 ms 127648 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
const long long INF = 1e18;
const int MAXK = 67;
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])
            continue;
        for(auto [adj,c]:con[nod])
        {
            if(adj==H)
            {
                if(tip[adj]==0)
                    dist[0][adj]=0;
                else if(tip[adj]==2)
                    dist[0][adj]=min(dist[0][adj], (cdist+(ld)c)/2);
                else
                    dist[0][adj]=min(dist[0][adj], cdist+c);
            }
            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(tip[adj]==1)
            {
                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 12 ms 29276 KB Correct.
2 Correct 13 ms 29272 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Correct.
2 Correct 16 ms 29276 KB Correct.
3 Correct 15 ms 29424 KB Correct.
4 Correct 16 ms 29276 KB Correct.
5 Correct 16 ms 29320 KB Correct.
6 Correct 16 ms 30044 KB Correct.
7 Correct 19 ms 29920 KB Correct.
8 Correct 10 ms 30816 KB Correct.
9 Correct 15 ms 29272 KB Correct.
10 Correct 17 ms 29276 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29276 KB Correct.
2 Correct 17 ms 29276 KB Correct.
3 Correct 22 ms 29476 KB Correct.
4 Correct 16 ms 29276 KB Correct.
5 Correct 16 ms 29272 KB Correct.
6 Correct 5 ms 30044 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 35724 KB Correct.
2 Correct 152 ms 29540 KB Correct.
3 Correct 134 ms 29596 KB Correct.
4 Correct 136 ms 29528 KB Correct.
5 Correct 119 ms 29364 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Correct.
2 Correct 15 ms 29376 KB Correct.
3 Correct 16 ms 29348 KB Correct.
4 Correct 16 ms 30300 KB Correct.
5 Correct 14 ms 29332 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29276 KB Correct.
2 Correct 14 ms 29276 KB Correct.
3 Correct 26 ms 34652 KB Correct.
4 Correct 11 ms 30044 KB Correct.
5 Correct 16 ms 29276 KB Correct.
6 Correct 15 ms 29428 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 29864 KB Correct.
2 Correct 27 ms 30344 KB Correct.
3 Correct 435 ms 28208 KB Correct.
4 Correct 380 ms 27524 KB Correct.
5 Correct 503 ms 69032 KB Correct.
6 Correct 249 ms 51896 KB Correct.
7 Correct 358 ms 29160 KB Correct.
8 Correct 353 ms 29740 KB Correct.
9 Correct 139 ms 30184 KB Correct.
10 Correct 139 ms 30220 KB Correct.
11 Correct 360 ms 29972 KB Correct.
12 Correct 157 ms 30240 KB Correct.
13 Correct 156 ms 30256 KB Correct.
14 Correct 295 ms 32020 KB Correct.
15 Correct 350 ms 30828 KB Correct.
16 Correct 139 ms 30184 KB Correct.
17 Correct 165 ms 30132 KB Correct.
18 Correct 164 ms 30064 KB Correct.
19 Correct 372 ms 29832 KB Correct.
20 Correct 13 ms 29532 KB Correct.
21 Correct 13 ms 29652 KB Correct.
22 Correct 25 ms 31952 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 58124 KB Correct.
2 Correct 69 ms 59084 KB Correct.
3 Correct 371 ms 64600 KB Correct.
4 Correct 793 ms 58244 KB Correct.
5 Correct 1941 ms 127648 KB Correct.
6 Correct 959 ms 127400 KB Correct.
7 Correct 895 ms 73924 KB Correct.
8 Correct 954 ms 57140 KB Correct.
9 Correct 508 ms 59984 KB Correct.
10 Correct 494 ms 59688 KB Correct.
11 Correct 2186 ms 56232 KB Correct.
12 Correct 502 ms 59492 KB Correct.
13 Correct 557 ms 59344 KB Correct.
14 Correct 2956 ms 126944 KB Correct.
15 Correct 2658 ms 68796 KB Correct.
16 Correct 1473 ms 63464 KB Correct.
17 Correct 1117 ms 59812 KB Correct.
18 Correct 469 ms 60020 KB Correct.
19 Correct 593 ms 59340 KB Correct.
20 Correct 613 ms 59636 KB Correct.
21 Correct 1326 ms 60292 KB Correct.
22 Correct 40 ms 56664 KB Correct.
23 Correct 47 ms 57552 KB Correct.
24 Correct 76 ms 66248 KB Correct.