oj.uz

Submission #1056483

# Submission time Handle Problem Language Result Execution time Memory
1056483 2024-08-13T09:40:49 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 382476 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])
            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 19 ms 50268 KB Correct.
2 Correct 30 ms 50268 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50264 KB Correct.
2 Correct 32 ms 50268 KB Correct.
3 Correct 26 ms 50268 KB Correct.
4 Correct 31 ms 50416 KB Correct.
5 Correct 28 ms 50408 KB Correct.
6 Correct 33 ms 51168 KB Correct.
7 Correct 31 ms 51032 KB Correct.
8 Correct 24 ms 53848 KB Correct.
9 Correct 25 ms 50268 KB Correct.
10 Correct 26 ms 50268 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50268 KB Correct.
2 Correct 28 ms 50268 KB Correct.
3 Correct 27 ms 50268 KB Correct.
4 Correct 26 ms 50332 KB Correct.
5 Correct 30 ms 50328 KB Correct.
6 Correct 10 ms 51032 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 62156 KB Correct.
2 Correct 290 ms 50928 KB Correct.
3 Correct 248 ms 50816 KB Correct.
4 Correct 261 ms 50752 KB Correct.
5 Correct 222 ms 50264 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 50524 KB Correct.
2 Correct 26 ms 50432 KB Correct.
3 Correct 25 ms 50444 KB Correct.
4 Correct 24 ms 51300 KB Correct.
5 Correct 25 ms 50268 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50264 KB Correct.
2 Correct 22 ms 50512 KB Correct.
3 Correct 50 ms 57680 KB Correct.
4 Correct 19 ms 51272 KB Correct.
5 Correct 25 ms 50264 KB Correct.
6 Correct 24 ms 50268 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 51472 KB Correct.
2 Correct 44 ms 52328 KB Correct.
3 Correct 784 ms 44444 KB Correct.
4 Correct 646 ms 45232 KB Correct.
5 Correct 1035 ms 124324 KB Correct.
6 Correct 438 ms 88236 KB Correct.
7 Correct 621 ms 50688 KB Correct.
8 Correct 628 ms 50980 KB Correct.
9 Correct 254 ms 52140 KB Correct.
10 Correct 258 ms 52376 KB Correct.
11 Correct 611 ms 51040 KB Correct.
12 Correct 258 ms 52036 KB Correct.
13 Correct 277 ms 52008 KB Correct.
14 Correct 502 ms 52992 KB Correct.
15 Correct 635 ms 52672 KB Correct.
16 Correct 261 ms 51836 KB Correct.
17 Correct 296 ms 51836 KB Correct.
18 Correct 317 ms 51864 KB Correct.
19 Correct 699 ms 51332 KB Correct.
20 Correct 22 ms 50672 KB Correct.
21 Correct 28 ms 51132 KB Correct.
22 Correct 41 ms 54984 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 121520 KB Correct.
2 Correct 142 ms 121044 KB Correct.
3 Correct 851 ms 122448 KB Correct.
4 Correct 1557 ms 118092 KB Correct.
5 Execution timed out 3061 ms 382476 KB Time limit exceeded
6 Halted 0 ms 0 KB -