oj.uz

Submission #1056470

# Submission time Handle Problem Language Result Execution time Memory
1056470 2024-08-13T09:35:51 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 383636 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];

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 50268 KB Correct.
2 Correct 21 ms 50412 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50268 KB Correct.
2 Correct 28 ms 50444 KB Correct.
3 Correct 26 ms 50268 KB Correct.
4 Correct 29 ms 50268 KB Correct.
5 Correct 28 ms 50436 KB Correct.
6 Correct 30 ms 51032 KB Correct.
7 Correct 32 ms 51032 KB Correct.
8 Correct 17 ms 53852 KB Correct.
9 Correct 27 ms 50340 KB Correct.
10 Correct 27 ms 50268 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50408 KB Correct.
2 Correct 29 ms 50264 KB Correct.
3 Correct 34 ms 50268 KB Correct.
4 Correct 27 ms 50268 KB Correct.
5 Correct 28 ms 50336 KB Correct.
6 Correct 9 ms 51036 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 66760 KB Correct.
2 Correct 600 ms 51212 KB Correct.
3 Correct 518 ms 51244 KB Correct.
4 Correct 559 ms 51136 KB Correct.
5 Correct 486 ms 50436 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50268 KB Correct.
2 Correct 31 ms 50264 KB Correct.
3 Correct 26 ms 50252 KB Correct.
4 Correct 24 ms 51208 KB Correct.
5 Correct 28 ms 50268 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 50264 KB Correct.
2 Correct 26 ms 50524 KB Correct.
3 Correct 44 ms 57804 KB Correct.
4 Correct 19 ms 51288 KB Correct.
5 Correct 25 ms 50328 KB Correct.
6 Correct 24 ms 50520 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 52268 KB Correct.
2 Correct 75 ms 53356 KB Correct.
3 Correct 1076 ms 43548 KB Correct.
4 Correct 1020 ms 45652 KB Correct.
5 Correct 1545 ms 125348 KB Correct.
6 Correct 537 ms 89256 KB Correct.
7 Correct 1008 ms 50656 KB Correct.
8 Correct 1090 ms 51392 KB Correct.
9 Correct 453 ms 52228 KB Correct.
10 Correct 487 ms 52372 KB Correct.
11 Correct 1092 ms 51016 KB Correct.
12 Correct 475 ms 52048 KB Correct.
13 Correct 478 ms 52308 KB Correct.
14 Correct 716 ms 55816 KB Correct.
15 Correct 961 ms 52800 KB Correct.
16 Correct 449 ms 52100 KB Correct.
17 Correct 546 ms 52056 KB Correct.
18 Correct 532 ms 52056 KB Correct.
19 Correct 1475 ms 52232 KB Correct.
20 Correct 40 ms 50676 KB Correct.
21 Correct 41 ms 51072 KB Correct.
22 Correct 51 ms 56780 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2401 ms 122016 KB Correct.
2 Correct 315 ms 127956 KB Correct.
3 Correct 906 ms 122580 KB Correct.
4 Correct 2547 ms 122896 KB Correct.
5 Execution timed out 3061 ms 383636 KB Time limit exceeded
6 Halted 0 ms 0 KB -