Submission #750264

#	Time	Username	Problem	Language	Result	Execution time	Memory
750264		blue	Cyberland (APIO23_cyberland)	C++17	97 / 100	3064 ms	30140 KiB

cyberland

#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pid = pair<int, double>;

#define sz(x) int(x.size())






int N, M, K;
int H;
vi x, y, c, arr;

vector<pid>* edge;

//i = not halved yet, i + N = halved

vi reachable;


vector<double> dijkstra(vector<double> dist)
{
    priority_queue< pair<double, int> > tbv;
    for(int i = 0; i < 2*N; i++)
    {
        tbv.push({-dist[i], i});
    }

    while(!tbv.empty())
    {
        int u = tbv.top().second;

        if(dist[u] < -tbv.top().first)
        {
            tbv.pop();
            continue;
        }
        else
        {    
            tbv.pop();
        }


        if(u == H || u == H+N)
            continue;

        for(pid vp : edge[u])
        {
            int v = vp.first;
            if(dist[v] <= dist[u] + vp.second)
                continue;

            // tbv.erase({dist[v], v});

            dist[v] = dist[u] + vp.second;

            tbv.push({-dist[v], v});
        }
    } 

    return dist;
}







double solve(int N_, int M_, int K_, int H_, vi x_, vi y_, vi c_, vi arr_) 
{
    N = N_;
    M = M_;
    K = K_;
    H = H_;

    x = x_;
    y = y_;
    c = c_;
    arr = arr_;

    edge = new vector<pid>[2*N];

    for(int j = 0; j < M; j++)
    {
        edge[x[j]].push_back({y[j], c[j]});
        edge[y[j]].push_back({x[j], c[j]});

        edge[N+x[j]].push_back({y[j], c[j]});
        edge[N+y[j]].push_back({x[j], c[j]});
    }



    vector<double> dist(2*N, double(2'000'000'000) * double(M + 1));

    dist[0] = 0;

    reachable = vi(N, 1);

    dist = dijkstra(dist);

    for(int i = 0; i < N; i++)
        if(arr[i] == 0 && dist[i] < double(1'500'000'000) * double(M + 1))
            dist[i] = double(0);


    for(int i = 0; i < N; i++)
        if(dist[i] >= double(1'500'000'000) * double(M+1))
            reachable[i] = 0;



    K = min(K, 70);

    // K = 0;
    for(int k = 1; k <= K; k++)
    {
        dist = dijkstra(dist);

        for(int i = 0; i < N; i++)
        {
            if(arr[i] == 2)
            {
                dist[i+N] = dist[i] / double(2);
                dist[i] = double(2'000'000'000) * double(M + 1);
            }
        }

        for(int i = 0; i < N; i++)
            if(!reachable[i])
                dist[i] = dist[i+N] = double(2'000'000'000) * double(M + 1);
    } 

    dist = dijkstra(dist);
    for(int i = 0; i < N; i++)
            if(!reachable[i])
                dist[i] = double(2'000'000'000) * double(M + 1);


    if(!reachable[H])
        return -1;
    else
        return dist[H];
}

• 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: 0 / 3