Submission #771948

#	Time	Username	Problem	Language	Result	Execution time	Memory
771948		Tenis0206	Cyberland (APIO23_cyberland)	C++17	100 / 100	1878 ms	124080 KiB

cyberland

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int kmax = 120;
const long long oo = LLONG_MAX;

int n,m,k,f;

int tip[nmax + 5];

double d[nmax + 5][kmax + 5];
bool sel[nmax + 5][kmax + 5];

vector<pair<int,int>> G[nmax + 5];

vector<int> l;

typedef pair<pair<int,double>,int> pi;

void add_zero(int nod)
{
    sel[nod][0] = true;
    if(tip[nod]==0)
    {
        l.push_back(nod);
    }
    if(nod==f)
    {
        return;
    }
    for(auto it : G[nod])
    {
        if(sel[it.first][0])
        {
            continue;
        }
        add_zero(it.first);
    }
}

void Dijkstra()
{
    priority_queue <pi,vector<pi>,greater<pi>> h;
    for(int i=0;i<n;i++)
    {
        for(int p=0;p<=min(kmax,k);p++)
        {
            d[i][p] = oo;
            sel[i][p] = false;
        }
    }
    d[0][0] = 0;
    h.push({{0,0},0});
    l.clear();
    add_zero(0);
    if(!sel[f][0])
    {
        d[f][0] = -1;
        return;
    }
    for(int i=0;i<n;i++)
    {
        sel[i][0] = false;
    }
    for(auto it : l)
    {
        d[it][0] = 0;
        h.push({{0,0},it});
    }
    while(!h.empty())
    {
        while(!h.empty() && sel[h.top().second][h.top().first.first])
        {
            h.pop();
        }
        if(h.empty())
        {
            return;
        }
        int nod = h.top().second;
        int nr = h.top().first.first;
        h.pop();
        sel[nod][nr] = true;
        if(nod==f)
        {
            continue;
        }
        for(auto it : G[nod])
        {
            double new_t = d[nod][nr] + it.second;
            if(tip[it.first]==0)
            {
                continue;
            }
            if(new_t < d[it.first][nr])
            {
                d[it.first][nr] = new_t;
                h.push({{nr,d[it.first][nr]},it.first});
            }
            if(tip[it.first]==2 && nr < min(kmax,k))
            {
                if(new_t * 0.5 < d[it.first][nr + 1])
                {
                    d[it.first][nr+1] = new_t * 0.5;
                    h.push({{nr+1,d[it.first][nr+1]},it.first});
                }
            }
        }
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    n = N, m = M, k = K, f = H;
    for(int i=0;i<m;i++)
    {
        G[x[i]].push_back({y[i],c[i]});
        G[y[i]].push_back({x[i],c[i]});
    }
    for(int i=0;i<n;i++)
    {
        tip[i] = arr[i];
    }
    Dijkstra();
    for(int i=0;i<n;i++)
    {
        G[i].clear();
    }
    double rez = oo;
    for(int p=0;p<=min(kmax,k);p++)
    {
        rez = min(rez, d[f][p]);
    }
    return rez;
}

• 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