Submission #982434

#	Time	Username	Problem	Language	Result	Execution time	Memory
982434		Kenjikrab	Cyberland (APIO23_cyberland)	C++17	0 / 100	3063 ms	37724 KiB

cyberland

#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][30];
vector<pair<int,db>> node[n_max];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    db ans=DBL_MAX;
    for(int i=0;i<N;i++)for(int j=0;j<=K;j++)len[i][j]=DBL_MAX;
    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]});
    }
    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;
    q.push({{0,1},{K,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(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(v==0)ans=min(ans,nl);
            if(arr[v]==0)
            {
                if(len[v][k]>nl)
                {
                    for(int i=k;i<=K;i++)len[v][i]=nl;
                    ans=min(ans,nl);
                    continue;
                }
            }
            else if(arr[v]==2&&k>=1)
            {
                if(len[v][k-1]>nl)
                {
                    for(int i=k-1;i<=K;i++)len[v][i]=nl;
                    q.push({{nl,cost/2},{k-1,v}});
                }
                continue;
            }
            else
            {
                if(len[v][k]>nl)
                {
                    for(int i=k;i<=K;i++)len[v][i]=nl;
                    q.push({{nl,cost},{k,v}});
                }
            }
        }

    }
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3