oj.uz

Submission #1056489

# Submission time Handle Problem Language Result Execution time Memory
1056489 2024-08-13T09:42:45 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 559 ms 66476 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
const long long INF = 1e18;
const int MAXK = 65;
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 20 ms 27856 KB Correct.
2 Correct 12 ms 27740 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27816 KB Correct.
2 Correct 23 ms 27856 KB Correct.
3 Correct 16 ms 27872 KB Correct.
4 Correct 17 ms 27740 KB Correct.
5 Correct 18 ms 27740 KB Correct.
6 Correct 21 ms 28508 KB Correct.
7 Correct 21 ms 28508 KB Correct.
8 Correct 10 ms 29276 KB Correct.
9 Correct 16 ms 27764 KB Correct.
10 Correct 15 ms 27788 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27740 KB Correct.
2 Correct 17 ms 27992 KB Correct.
3 Correct 16 ms 27740 KB Correct.
4 Correct 29 ms 27740 KB Correct.
5 Correct 17 ms 27740 KB Correct.
6 Correct 9 ms 28252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 34092 KB Correct.
2 Correct 159 ms 28036 KB Correct.
3 Correct 132 ms 28060 KB Correct.
4 Correct 137 ms 27960 KB Correct.
5 Correct 118 ms 27820 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27736 KB Correct.
2 Correct 15 ms 27740 KB Correct.
3 Correct 15 ms 27932 KB Correct.
4 Correct 16 ms 28712 KB Correct.
5 Correct 13 ms 27748 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27916 KB Correct.
2 Correct 14 ms 27740 KB Correct.
3 Correct 25 ms 33256 KB Correct.
4 Correct 12 ms 28508 KB Correct.
5 Correct 15 ms 27740 KB Correct.
6 Correct 15 ms 27740 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 28340 KB Correct.
2 Correct 23 ms 28832 KB Correct.
3 Correct 408 ms 26716 KB Correct.
4 Correct 361 ms 25984 KB Correct.
5 Correct 491 ms 66476 KB Correct.
6 Correct 245 ms 50040 KB Correct.
7 Correct 361 ms 27572 KB Correct.
8 Correct 353 ms 28204 KB Correct.
9 Correct 139 ms 28780 KB Correct.
10 Correct 140 ms 28676 KB Correct.
11 Correct 343 ms 28108 KB Correct.
12 Correct 142 ms 28732 KB Correct.
13 Correct 165 ms 28684 KB Correct.
14 Correct 295 ms 30516 KB Correct.
15 Correct 365 ms 29472 KB Correct.
16 Correct 135 ms 28636 KB Correct.
17 Correct 162 ms 28592 KB Correct.
18 Correct 178 ms 28500 KB Correct.
19 Correct 379 ms 28280 KB Correct.
20 Correct 13 ms 27736 KB Correct.
21 Correct 14 ms 28208 KB Correct.
22 Correct 23 ms 30160 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 56500 KB Correct.
2 Correct 67 ms 57668 KB Correct.
3 Incorrect 360 ms 63056 KB Wrong Answer.
4 Halted 0 ms 0 KB -