oj.uz

Submission #756218

# Submission time Handle Problem Language Result Execution time Memory
756218 2023-06-11T10:16:01 Z activedeltorre Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 63696 KB 
#include <vector>
#include <iostream>
#include <queue>
#include <iomanip>
#include "cyberland.h"
using namespace std;
long double inf=1e17;
double dp[100005][70];
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,60);
    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:39: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]
   39 |             for(i=0; i<adj[curr].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3368 KB Correct.
2 Correct 26 ms 3284 KB Correct.
3 Correct 28 ms 3348 KB Correct.
4 Correct 26 ms 3328 KB Correct.
5 Correct 27 ms 3352 KB Correct.
6 Correct 27 ms 8684 KB Correct.
7 Correct 35 ms 8580 KB Correct.
8 Correct 23 ms 14836 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 3252 KB Correct.
2 Correct 28 ms 3284 KB Correct.
3 Correct 26 ms 3360 KB Correct.
4 Correct 26 ms 2772 KB Correct.
5 Correct 26 ms 2776 KB Correct.
6 Correct 8 ms 7636 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 38228 KB Correct.
2 Correct 460 ms 3248 KB Correct.
3 Correct 396 ms 3336 KB Correct.
4 Correct 422 ms 3336 KB Correct.
5 Correct 395 ms 2760 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3356 KB Correct.
2 Correct 25 ms 3316 KB Correct.
3 Correct 24 ms 3352 KB Correct.
4 Correct 27 ms 8788 KB Correct.
5 Correct 23 ms 2776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3412 KB Correct.
2 Correct 22 ms 3304 KB Correct.
3 Correct 59 ms 49200 KB Correct.
4 Correct 19 ms 7252 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 22 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 3308 KB Correct.
2 Correct 81 ms 3764 KB Correct.
3 Correct 1771 ms 61292 KB Correct.
4 Correct 1693 ms 15992 KB Correct.
5 Correct 1926 ms 27596 KB Correct.
6 Correct 694 ms 12796 KB Correct.
7 Correct 1579 ms 17320 KB Correct.
8 Correct 1648 ms 4912 KB Correct.
9 Correct 504 ms 3444 KB Correct.
10 Correct 531 ms 3408 KB Correct.
11 Correct 1643 ms 3848 KB Correct.
12 Correct 535 ms 3324 KB Correct.
13 Correct 534 ms 3416 KB Correct.
14 Correct 1269 ms 31280 KB Correct.
15 Correct 1735 ms 10324 KB Correct.
16 Correct 501 ms 3404 KB Correct.
17 Correct 658 ms 3328 KB Correct.
18 Correct 603 ms 3404 KB Correct.
19 Correct 1602 ms 3296 KB Correct.
20 Correct 48 ms 2748 KB Correct.
21 Correct 42 ms 3216 KB Correct.
22 Correct 64 ms 3668 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1719 ms 3412 KB Correct.
2 Correct 228 ms 3800 KB Correct.
3 Execution timed out 3090 ms 63696 KB Time limit exceeded
4 Halted 0 ms 0 KB -