oj.uz

Submission #982522

# Submission time Handle Problem Language Result Execution time Memory
982522 2024-05-14T10:44:10 Z Kenjikrab Cyberland (APIO23_cyberland) C++17
100 / 100
 402 ms 172628 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#define fi first 
#define se second
#define db long double
using namespace std;
int const n_max=1e5+10;
db len[n_max][100];
vector<pair<int,db>> node[n_max];
bitset<n_max> canend;
db ans=DBL_MAX;

void reset(int N,int K)
{
    for(int i=0;i<=N;i++)for(int j=0;j<=K;j++)len[i][j]=DBL_MAX;
    for(int i=0;i<=N;i++)node[i].clear();
    canend.reset();
    ans=DBL_MAX;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    K=min(K,99);
    if(H==0||arr[H]==0)return 0;
    reset(N,K);
    for(int i=0;i<M;i++)
    {
        node[x[i]].push_back({y[i],(db)c[i]});
        node[y[i]].push_back({x[i],(db)c[i]});
    }
    canend[0]=true;
    queue<int> qq;
    qq.push(0);
    while(!qq.empty())
    {
        int u=qq.front();
        qq.pop();
        for(auto it:node[u])
        {
            int v=it.fi;
            if(canend[v]||v==H)continue;
            canend[v]=true;
            qq.push(v);
        }
    }
    priority_queue<pair<pair<db,db>,pair<int,int>>,vector<pair<pair<db,db>,pair<int,int>>>,
    greater<pair<pair<db,db>,pair<int,int>>>> q;
    if(arr[H]!=2&&K>=1)q.push({{0,1},{K,H}});
    else q.push({{0,0.5},{K-1,H}});
    //for(int i=0;i<=K;i++)len[H][i]=0;
    while(!q.empty())
    {
        db l=q.top().fi.fi,cost=q.top().fi.se;
        int k=q.top().se.fi,u=q.top().se.se;
        q.pop();
        //cout<<l<<" "<<cost<<" "<<k<<" "<<u<<endl;
        if(l>ans)continue;
        if(len[u][k]<l)continue;
        if(u==H&&l!=0)continue;
        for(auto it:node[u])
        {
            int v=it.fi;
            db nl=it.se*cost+l;
            if(nl>ans)continue;
            if(!canend[v])continue;
            if(v==0)ans=nl;
            if(arr[v]==0)
            {
                ans=nl;
                if(len[v][k]>nl)
                {
                    len[v][k]=nl;
                    continue;
                }
            }
            else if(arr[v]==2&&k>=1)
            {
                if(len[v][k-1]>nl)
                {
                    len[v][k-1]=nl;
                    q.push({{nl,cost/2},{k-1,v}});
                    //cout<<v<<endl;
                }
                continue;
            }
            else
            {
                if(len[v][k]>nl)
                {
                    len[v][k]=nl;
                    q.push({{nl,cost},{k,v}});
                    //cout<<v<<endl;
                }
            }
        }
    }
    if(ans==DBL_MAX)return -1;
    else return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4700 KB Correct.
2 Correct 20 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4952 KB Correct.
2 Correct 24 ms 4952 KB Correct.
3 Correct 23 ms 4952 KB Correct.
4 Correct 24 ms 4952 KB Correct.
5 Correct 24 ms 4956 KB Correct.
6 Correct 22 ms 20316 KB Correct.
7 Correct 30 ms 20308 KB Correct.
8 Correct 17 ms 35676 KB Correct.
9 Correct 24 ms 4800 KB Correct.
10 Correct 24 ms 4700 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4956 KB Correct.
2 Correct 22 ms 4972 KB Correct.
3 Correct 21 ms 4956 KB Correct.
4 Correct 24 ms 4788 KB Correct.
5 Correct 24 ms 4700 KB Correct.
6 Correct 13 ms 17752 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 100356 KB Correct.
2 Correct 23 ms 4696 KB Correct.
3 Correct 21 ms 4696 KB Correct.
4 Correct 22 ms 4700 KB Correct.
5 Correct 25 ms 4700 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4952 KB Correct.
2 Correct 27 ms 5212 KB Correct.
3 Correct 26 ms 4956 KB Correct.
4 Correct 28 ms 21380 KB Correct.
5 Correct 24 ms 4796 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4956 KB Correct.
2 Correct 23 ms 5212 KB Correct.
3 Correct 70 ms 130640 KB Correct.
4 Correct 18 ms 16476 KB Correct.
5 Correct 23 ms 4804 KB Correct.
6 Correct 22 ms 5072 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4952 KB Correct.
2 Correct 4 ms 7004 KB Correct.
3 Correct 84 ms 162624 KB Correct.
4 Correct 47 ms 40788 KB Correct.
5 Correct 55 ms 69716 KB Correct.
6 Correct 37 ms 28240 KB Correct.
7 Correct 47 ms 44760 KB Correct.
8 Correct 48 ms 9388 KB Correct.
9 Correct 25 ms 5208 KB Correct.
10 Correct 21 ms 5212 KB Correct.
11 Correct 46 ms 5200 KB Correct.
12 Correct 23 ms 4952 KB Correct.
13 Correct 22 ms 4956 KB Correct.
14 Correct 54 ms 82524 KB Correct.
15 Correct 43 ms 24912 KB Correct.
16 Correct 23 ms 4952 KB Correct.
17 Correct 27 ms 5212 KB Correct.
18 Correct 23 ms 4952 KB Correct.
19 Correct 43 ms 4956 KB Correct.
20 Correct 3 ms 4700 KB Correct.
21 Correct 3 ms 4700 KB Correct.
22 Correct 4 ms 5724 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5396 KB Correct.
2 Correct 11 ms 7256 KB Correct.
3 Correct 246 ms 172628 KB Correct.
4 Correct 68 ms 16204 KB Correct.
5 Correct 54 ms 71504 KB Correct.
6 Correct 32 ms 29784 KB Correct.
7 Correct 125 ms 65940 KB Correct.
8 Correct 64 ms 9040 KB Correct.
9 Correct 47 ms 5980 KB Correct.
10 Correct 45 ms 5992 KB Correct.
11 Correct 402 ms 5972 KB Correct.
12 Correct 47 ms 5972 KB Correct.
13 Correct 56 ms 5996 KB Correct.
14 Correct 193 ms 75084 KB Correct.
15 Correct 253 ms 88256 KB Correct.
16 Correct 64 ms 36436 KB Correct.
17 Correct 65 ms 11344 KB Correct.
18 Correct 50 ms 6132 KB Correct.
19 Correct 66 ms 6368 KB Correct.
20 Correct 50 ms 6028 KB Correct.
21 Correct 89 ms 6992 KB Correct.
22 Correct 6 ms 4700 KB Correct.
23 Correct 6 ms 4728 KB Correct.
24 Correct 4 ms 5720 KB Correct.