oj.uz

Submission #756222

# Submission time Handle Problem Language Result Execution time Memory
756222 2023-06-11T10:20:15 Z activedeltorre Cyberland (APIO23_cyberland) C++17
97 / 100
 1934 ms 51984 KB 
#include <vector>
#include <iostream>
#include <queue>
#include <iomanip>
#pragma GCC optimize ("O3") 
#include "cyberland.h"
using namespace std;
long double inf=1e17;
double dp[100005][55];
vector<pair<int,int> >adj[100005];
priority_queue<pair<int,pair<double,int> > >pq;
double solve(int n,int m,int k,int fs,vector<int>x,vector<int>y,vector<int>cst,vector<int>arr)
{
    int i,j;
    k=min(k,30);
    for(i=0; i<m; i++)
    {
        adj[x[i]].push_back({y[i],cst[i]});
        adj[y[i]].push_back({x[i],cst[i]});
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<=k; j++)
        {
            dp[i][j]=inf;
        }
    }
    dp[0][0]=0;
    pq.push({0,{0,0}});
    int layer,curr,vec;
    double timp,cost;
    while(pq.size())
    {
        layer=pq.top().first;
        timp=pq.top().second.first;
        curr=pq.top().second.second;
        pq.pop();
        if(dp[curr][layer]==-timp && curr!=fs)
        {
            for(i=0; i<adj[curr].size(); i++)
            {
                vec=adj[curr][i].first;
                cost=adj[curr][i].second;
                if(arr[vec]==0 && dp[vec][layer]!=0)
                {
                    dp[vec][layer]=0;
                    pq.push({layer,{0,vec}});
                }
                else if(dp[curr][layer]+cost<dp[vec][layer])
                {
                    dp[vec][layer]=dp[curr][layer]+cost;
                    pq.push({layer,{-dp[vec][layer],vec}});
                }
                if(arr[vec]==2 && dp[curr][layer]+cost<dp[vec][layer+1]*2)
                {
                    dp[vec][layer+1]=(dp[curr][layer]+cost)/2;
                    pq.push({layer+1,{-dp[vec][layer+1],vec}});
                }
            }
        }
    }
    double sol=inf;
    for(i=0; i<=k; i++)
    {
        sol=min(sol,dp[fs][i]);
    }
    for(i=0;i<=n;i++)
    {
        adj[i].clear();
    }
    if(sol==inf)
    {
        return -1;
    }
    return sol;
}
/*
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int N,M,K,H;
        cin>>N>>M>>K>>H;
        std::vector<int> x(M);
        std::vector<int> y(M);
        std::vector<int> c(M);
        std::vector<int> arr(N);
        for (int i=0; i<N; i++)
            cin>>arr[i];
        for (int i=0; i<M; i++)
        {
            cin>>x[i]>>y[i]>>c[i];
        }
        cout<<setprecision(12)<<solve(N, M, K, H, x, y, c, arr)<<'\n';
    }
}
*/

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(i=0; i<adj[curr].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2772 KB Correct.
2 Correct 21 ms 2824 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3204 KB Correct.
2 Correct 26 ms 3180 KB Correct.
3 Correct 25 ms 3156 KB Correct.
4 Correct 26 ms 3224 KB Correct.
5 Correct 26 ms 3208 KB Correct.
6 Correct 30 ms 7492 KB Correct.
7 Correct 31 ms 7524 KB Correct.
8 Correct 18 ms 12500 KB Correct.
9 Correct 23 ms 2772 KB Correct.
10 Correct 23 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3112 KB Correct.
2 Correct 26 ms 3232 KB Correct.
3 Correct 26 ms 3240 KB Correct.
4 Correct 25 ms 2772 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 9 ms 6612 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 31480 KB Correct.
2 Correct 500 ms 3404 KB Correct.
3 Correct 433 ms 3196 KB Correct.
4 Correct 452 ms 3292 KB Correct.
5 Correct 438 ms 2644 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3312 KB Correct.
2 Correct 24 ms 3272 KB Correct.
3 Correct 24 ms 3204 KB Correct.
4 Correct 27 ms 7668 KB Correct.
5 Correct 21 ms 2768 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3284 KB Correct.
2 Correct 22 ms 3264 KB Correct.
3 Correct 55 ms 40264 KB Correct.
4 Correct 20 ms 6416 KB Correct.
5 Correct 26 ms 2644 KB Correct.
6 Correct 26 ms 3284 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 3288 KB Correct.
2 Correct 94 ms 3580 KB Correct.
3 Correct 1785 ms 50160 KB Correct.
4 Correct 1680 ms 13624 KB Correct.
5 Correct 1934 ms 23500 KB Correct.
6 Correct 758 ms 11504 KB Correct.
7 Correct 1640 ms 14488 KB Correct.
8 Correct 1763 ms 4524 KB Correct.
9 Correct 531 ms 3444 KB Correct.
10 Correct 545 ms 3328 KB Correct.
11 Correct 1754 ms 3676 KB Correct.
12 Correct 565 ms 3400 KB Correct.
13 Correct 565 ms 3360 KB Correct.
14 Correct 1318 ms 25844 KB Correct.
15 Correct 1829 ms 8912 KB Correct.
16 Correct 530 ms 3352 KB Correct.
17 Correct 655 ms 3436 KB Correct.
18 Correct 634 ms 3280 KB Correct.
19 Correct 1749 ms 3308 KB Correct.
20 Correct 43 ms 2764 KB Correct.
21 Correct 43 ms 3112 KB Correct.
22 Correct 64 ms 3616 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 3228 KB Correct.
2 Correct 84 ms 3696 KB Correct.
3 Incorrect 1459 ms 51984 KB Wrong Answer.
4 Halted 0 ms 0 KB -