Submission #1203318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203318		rafsanamin2020	Cyberland (APIO23_cyberland)	C++17	15 / 100	19 ms	6724 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

// subtask 1

// ll ac(ll k, ll f)
// {
//     // cout << k << " " << f;
//     if (f == 0)
//     {
//         return 0;
//     }
//     else if (f == 2)
//     {
//         return k / 2;
//     }
//     else
//     {
//         return k;
//     }
// };

// ll _(ll k)
// {
//     return k == 2 ? 1 : 2;
// }

// ll solve(ll N, ll M, ll K, ll H, std::vector<ll> x, std::vector<ll> y, std::vector<ll> c, std::vector<ll> arr)
// {
//     ll MAX = (5.0e10 + 0.1);
//     vector<vector<ll>> C(3, vector<ll>(3, MAX));
//     vector<vector<bool>> V(3, vector<bool>(3, false));

//     for (ll i = 0; i < M; i++)
//     {
//         C[x[i]][y[i]] = min(C[x[i]][y[i]], (ll)c[i]);
//         C[y[i]][x[i]] = min(C[y[i]][x[i]], (ll)c[i]);
//         V[x[i]][y[i]] = true;
//         V[y[i]][x[i]] = true;
//     }

//     if ((!V[0][H] && !V[0][_(H)]) || (!V[0][H] && !V[H][_(H)]))
//     {
//         return -1;
//     }

//     // cout << C[0][2] << " ___" << "\n";

//     return min(ac(C[0][_(H)], arr[_(H)]) + C[_(H)][H], C[0][H]);
// }

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{
    vector<vector<pair<ll, ll>>> adj(N);
    vector<ll> cost(N, 5e17);
    vector<bool> visited(N, false);

    ll minCost = 5e17;

    for (ll i = 0; i < M; i++)
    {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    priority_queue<pair<ll, ll>> pq;

    cost[H] = 0;
    pq.push({0, H});

    // cout << pq.top().first << " \n";
    while (!pq.empty())
    {
        ll cst = -pq.top().first;
        ll node = pq.top().second;
        pq.pop();
        visited[node] = true;

        if (arr[node] == 0)
        {
            minCost = min(minCost, cost[node]);
        }

        for (ll i = 0; i < adj[node].size(); i++)
        {
            ll v = adj[node][i].first;
            ll w = adj[node][i].second;

            if (cost[v] > cost[node] + w)
            {
                cost[v] = cost[node] + w;
                pq.push({-cost[v], v});
            }
        }
    }

    minCost = min(minCost, cost[0]);

    return visited[0] ? minCost : -1;
}

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