oj.uz

Submission #1056493

# Submission time Handle Problem Language Result Execution time Memory
1056493 2024-08-13T09:45:58 Z alexdd Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 128536 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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) {
    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 14 ms 29276 KB Correct.
2 Correct 14 ms 29288 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29272 KB Correct.
2 Correct 16 ms 29424 KB Correct.
3 Correct 15 ms 29276 KB Correct.
4 Correct 16 ms 29424 KB Correct.
5 Correct 17 ms 29276 KB Correct.
6 Correct 15 ms 30040 KB Correct.
7 Correct 19 ms 30044 KB Correct.
8 Correct 10 ms 30824 KB Correct.
9 Correct 15 ms 29276 KB Correct.
10 Correct 15 ms 29272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29276 KB Correct.
2 Correct 16 ms 29420 KB Correct.
3 Correct 17 ms 29276 KB Correct.
4 Correct 16 ms 29352 KB Correct.
5 Correct 16 ms 29272 KB Correct.
6 Correct 7 ms 30044 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 35528 KB Correct.
2 Correct 154 ms 29596 KB Correct.
3 Correct 133 ms 29648 KB Correct.
4 Correct 146 ms 29532 KB Correct.
5 Correct 135 ms 29276 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29276 KB Correct.
2 Correct 19 ms 29528 KB Correct.
3 Correct 18 ms 29496 KB Correct.
4 Correct 15 ms 30236 KB Correct.
5 Correct 13 ms 29328 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29420 KB Correct.
2 Correct 17 ms 29428 KB Correct.
3 Correct 28 ms 34708 KB Correct.
4 Correct 11 ms 30044 KB Correct.
5 Correct 15 ms 29348 KB Correct.
6 Correct 17 ms 29460 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 29880 KB Correct.
2 Correct 23 ms 30372 KB Correct.
3 Correct 499 ms 28268 KB Correct.
4 Correct 373 ms 27576 KB Correct.
5 Correct 595 ms 68172 KB Correct.
6 Correct 247 ms 50872 KB Correct.
7 Correct 357 ms 29160 KB Correct.
8 Correct 359 ms 29748 KB Correct.
9 Correct 140 ms 30172 KB Correct.
10 Correct 157 ms 30252 KB Correct.
11 Correct 349 ms 29712 KB Correct.
12 Correct 143 ms 30192 KB Correct.
13 Correct 154 ms 30248 KB Correct.
14 Correct 327 ms 32104 KB Correct.
15 Correct 372 ms 31000 KB Correct.
16 Correct 138 ms 30216 KB Correct.
17 Correct 174 ms 30132 KB Correct.
18 Correct 165 ms 30180 KB Correct.
19 Correct 381 ms 29828 KB Correct.
20 Correct 13 ms 29428 KB Correct.
21 Correct 14 ms 29748 KB Correct.
22 Correct 23 ms 31892 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 58000 KB Correct.
2 Correct 71 ms 59172 KB Correct.
3 Correct 395 ms 64604 KB Correct.
4 Correct 812 ms 58244 KB Correct.
5 Correct 1994 ms 128536 KB Correct.
6 Correct 1014 ms 126280 KB Correct.
7 Correct 890 ms 73324 KB Correct.
8 Correct 977 ms 57252 KB Correct.
9 Correct 514 ms 59940 KB Correct.
10 Correct 527 ms 59488 KB Correct.
11 Correct 2312 ms 56236 KB Correct.
12 Correct 503 ms 59508 KB Correct.
13 Correct 561 ms 59340 KB Correct.
14 Execution timed out 3058 ms 127980 KB Time limit exceeded
15 Halted 0 ms 0 KB -