oj.uz

Submission #1056487

# Submission time Handle Problem Language Result Execution time Memory
1056487 2024-08-13T09:41:42 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 130568 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef 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 12 ms 27648 KB Correct.
2 Correct 12 ms 27608 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27484 KB Correct.
2 Correct 16 ms 27664 KB Correct.
3 Correct 15 ms 27572 KB Correct.
4 Correct 17 ms 27484 KB Correct.
5 Correct 16 ms 27640 KB Correct.
6 Correct 15 ms 28252 KB Correct.
7 Correct 25 ms 28252 KB Correct.
8 Correct 10 ms 29096 KB Correct.
9 Correct 16 ms 27596 KB Correct.
10 Correct 15 ms 27484 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27484 KB Correct.
2 Correct 17 ms 27484 KB Correct.
3 Correct 16 ms 27720 KB Correct.
4 Correct 17 ms 27484 KB Correct.
5 Correct 16 ms 27568 KB Correct.
6 Correct 7 ms 28252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 33888 KB Correct.
2 Correct 169 ms 27824 KB Correct.
3 Correct 132 ms 27876 KB Correct.
4 Correct 136 ms 27772 KB Correct.
5 Correct 119 ms 27604 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 27720 KB Correct.
2 Correct 16 ms 27676 KB Correct.
3 Correct 16 ms 27484 KB Correct.
4 Correct 17 ms 28508 KB Correct.
5 Correct 17 ms 27484 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27736 KB Correct.
2 Correct 19 ms 27740 KB Correct.
3 Correct 27 ms 33104 KB Correct.
4 Correct 11 ms 28252 KB Correct.
5 Correct 27 ms 27484 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 28220 KB Correct.
2 Correct 23 ms 28580 KB Correct.
3 Correct 425 ms 26484 KB Correct.
4 Correct 382 ms 25996 KB Correct.
5 Correct 517 ms 65704 KB Correct.
6 Correct 252 ms 48828 KB Correct.
7 Correct 354 ms 27368 KB Correct.
8 Correct 355 ms 28092 KB Correct.
9 Correct 140 ms 28444 KB Correct.
10 Correct 139 ms 28468 KB Correct.
11 Correct 342 ms 28012 KB Correct.
12 Correct 142 ms 28444 KB Correct.
13 Correct 156 ms 28480 KB Correct.
14 Correct 293 ms 30264 KB Correct.
15 Correct 351 ms 29272 KB Correct.
16 Correct 137 ms 28384 KB Correct.
17 Correct 165 ms 28336 KB Correct.
18 Correct 164 ms 28260 KB Correct.
19 Correct 374 ms 28084 KB Correct.
20 Correct 13 ms 27740 KB Correct.
21 Correct 14 ms 27956 KB Correct.
22 Correct 23 ms 30040 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 61528 KB Correct.
2 Correct 84 ms 61404 KB Correct.
3 Correct 395 ms 66900 KB Correct.
4 Correct 831 ms 60592 KB Correct.
5 Correct 2178 ms 130568 KB Correct.
6 Correct 1058 ms 129948 KB Correct.
7 Correct 939 ms 77360 KB Correct.
8 Correct 960 ms 61392 KB Correct.
9 Correct 543 ms 63544 KB Correct.
10 Correct 529 ms 62892 KB Correct.
11 Correct 2338 ms 59472 KB Correct.
12 Correct 543 ms 62876 KB Correct.
13 Correct 611 ms 62604 KB Correct.
14 Execution timed out 3050 ms 130248 KB Time limit exceeded
15 Halted 0 ms 0 KB -