oj.uz

Submission #1056503

# Submission time Handle Problem Language Result Execution time Memory
1056503 2024-08-13T09:49:17 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 128164 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int MAXK = 67;
vector<pair<int,int>> con[100005];
vector<int> tip;
double 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) {
    __builtin_ia32_ldmxcsr(40896);
    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<double,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())
    {
        double 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+(double)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 + (double)c)/2)
                {
                    dist[cnt+1][adj] = (cdist + (double)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}});
                }
            }
        }
    }
    double 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 13 ms 29276 KB Correct.
2 Correct 13 ms 29408 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29276 KB Correct.
2 Correct 17 ms 29444 KB Correct.
3 Correct 21 ms 29276 KB Correct.
4 Correct 17 ms 29276 KB Correct.
5 Correct 18 ms 29276 KB Correct.
6 Correct 17 ms 30196 KB Correct.
7 Correct 20 ms 30044 KB Correct.
8 Correct 11 ms 30664 KB Correct.
9 Correct 15 ms 29276 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 29444 KB Correct.
3 Correct 16 ms 29276 KB Correct.
4 Correct 16 ms 29340 KB Correct.
5 Correct 18 ms 29276 KB Correct.
6 Correct 6 ms 30044 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 35532 KB Correct.
2 Correct 157 ms 29592 KB Correct.
3 Correct 132 ms 29600 KB Correct.
4 Correct 139 ms 29600 KB Correct.
5 Correct 118 ms 29384 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29272 KB Correct.
2 Correct 15 ms 29276 KB Correct.
3 Correct 15 ms 29276 KB Correct.
4 Correct 16 ms 30552 KB Correct.
5 Correct 13 ms 29304 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29276 KB Correct.
2 Correct 14 ms 29396 KB Correct.
3 Correct 26 ms 34816 KB Correct.
4 Correct 11 ms 30196 KB Correct.
5 Correct 15 ms 29276 KB Correct.
6 Correct 15 ms 29520 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 29916 KB Correct.
2 Correct 23 ms 30368 KB Correct.
3 Correct 414 ms 28304 KB Correct.
4 Correct 369 ms 27684 KB Correct.
5 Correct 502 ms 67752 KB Correct.
6 Correct 245 ms 50364 KB Correct.
7 Correct 357 ms 29052 KB Correct.
8 Correct 356 ms 29816 KB Correct.
9 Correct 153 ms 30172 KB Correct.
10 Correct 141 ms 30260 KB Correct.
11 Correct 342 ms 29748 KB Correct.
12 Correct 153 ms 30304 KB Correct.
13 Correct 156 ms 30248 KB Correct.
14 Correct 318 ms 32056 KB Correct.
15 Correct 355 ms 31004 KB Correct.
16 Correct 138 ms 30136 KB Correct.
17 Correct 165 ms 30128 KB Correct.
18 Correct 168 ms 30032 KB Correct.
19 Correct 395 ms 29820 KB Correct.
20 Correct 13 ms 29532 KB Correct.
21 Correct 13 ms 29764 KB Correct.
22 Correct 23 ms 31880 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 58096 KB Correct.
2 Correct 78 ms 59184 KB Correct.
3 Correct 376 ms 64592 KB Correct.
4 Correct 818 ms 58264 KB Correct.
5 Correct 2207 ms 128164 KB Correct.
6 Correct 1155 ms 126880 KB Correct.
7 Correct 991 ms 73524 KB Correct.
8 Correct 957 ms 57196 KB Correct.
9 Correct 509 ms 59980 KB Correct.
10 Correct 570 ms 60032 KB Correct.
11 Correct 2268 ms 56500 KB Correct.
12 Correct 522 ms 59632 KB Correct.
13 Correct 594 ms 60456 KB Correct.
14 Execution timed out 3043 ms 126372 KB Time limit exceeded
15 Halted 0 ms 0 KB -