Submission #982522

#	Time	Username	Problem	Language	Result	Execution time	Memory
982522		Kenjikrab	Cyberland (APIO23_cyberland)	C++17	100 / 100	402 ms	172628 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][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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3