Submission #1202345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202345		rafsanamin2020	Cyberland (APIO23_cyberland)	C++17	0 / 100	12 ms	2116 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <iostream>

using namespace std;

// subtask 1

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

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

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)
{
    double MAX = (5.0e10 + 0.1);
    vector<vector<double>> C(3, vector<double>(3, MAX));
    vector<vector<bool>> V(3, vector<bool>(3, false));

    for (int i = 0; i < M; i++)
    {
        C[x[i]][y[i]] = min(C[x[i]][y[i]], (double)c[i]);
        C[y[i]][x[i]] = min(C[y[i]][x[i]], (double)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]);
}

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

// const double INF = 5e9 + 0.1;
// const int mxN = 1e5 + 100;
// vector<pair<int, int>> adj[mxN];

// vector<int> ar;
// double ans = INF;

// struct DSU
// {
//     vector<int> sz, par;
//     void init(int n)
//     {
//         sz.resize(n, 1);
//         par.resize(n);
//         for (int i = 1; i < n; ++i)
//             par[i] = i;
//     }
//     int findPar(int u)
//     {
//         if (par[u] == u)
//             return u;
//         return par[u] = findPar(par[u]);
//     }
//     void unite(int u, int v)
//     {
//         int upar = findPar(u);
//         int vpar = findPar(v);
//         if (upar == vpar)
//             return;
//         if (sz[upar] > sz[vpar])
//         {
//             par[vpar] = upar;
//             sz[upar] += sz[vpar];
//         }
//         else
//         {
//             par[upar] = vpar;
//             sz[vpar] += sz[upar];
//         }
//     }
// };

// double dfs(int u, int par, int h, double cost)
// {
//     if (u == h)
//         return cost;
//     if (ar[u] == 2)
//         cost /= 2;
//     else if (ar[u] == 0)
//         cost = 0;
//     double ans = INF;
//     for (auto it : adj[u])
//     {
//         if (it.first ^ par)
//         {
//             ans = min(ans, dfs(it.first, u, h, cost + it.second));
//         }
//     }
//     return ans;
// }

// double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
// {
//     ar = arr;
//     DSU ds;
//     ds.init(N + 5);
//     for (int i = 0; i <= N; ++i)
//         adj[i].clear();
//     for (int i = 0; i < M; ++i)
//     {
//         adj[x[i]].push_back({y[i], c[i]});
//         adj[y[i]].push_back({x[i], c[i]});
//         ds.unite(x[i], y[i]);
//     }
//     if (ds.findPar(0) != ds.findPar(H))
//         return -1;
//     return dfs(0, -1, H, 0);
// }

• 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