Submission #1203036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203036		VahanAbraham	Cyberland (APIO23_cyberland)	C++20	0 / 100	3099 ms	110356 KiB

cyberland

#include "cyberland.h"

#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>

#define ll long long
#define fr first
#define sc second
#define pb push_back

using namespace std;

const int N = 100005;
const ll oo = 1000000000000000, MOD = 1000000007;


vector<pair<int, int>> g[N];
double dist[N][30];

double solve(int n, int m, int k, int h, std::vector<int> vec1, std::vector<int> vec2, std::vector<int> vec3, std::vector<int> a) {
    for (int i = 0; i < n; ++i) {
        g[i].clear();
    }
    for (int i = 0; i < m; ++i) {
        g[vec1[i]].pb({ vec2[i],vec3[i] });
        g[vec2[i]].pb({ vec1[i],vec3[i] });
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dist[i][j] = oo;
        }
    }
    dist[0][0] = 0;
    set<pair<double, pair<int, int>>> st;
    st.insert({ dist[0][0],{0,0} });
    while (1) {
        int sz = st.size();
        if (sz == 0) {
            break;
        }
        auto it = st.begin();
        pair<double, pair<int, int>> p = (*it);
        st.erase(it);
        int k1 = p.sc.fr;
        int u = p.sc.sc;
        double val = p.fr;
        if (dist[u][k1] != val || u == h) {
            continue;
        }
        double val2 = val / (2.0);
        for (pair<int, int> num : g[u]) {
            int h = num.fr;
            int w = num.sc;
            if (k1 < k) {
                if (a[u] == 0) {
                    if (dist[h][k1 + 1] > w) {
                        dist[h][k1 + 1] = w;
                        st.insert({ dist[h][k1 + 1],{k1 + 1,h} });
                    }
                    if (dist[h][k1] > val + w) {
                        dist[h][k1] = val + w;
                        st.insert({ dist[h][k1],{k1,h} });
                    }
                }
                else {
                    if (a[u] == 2) {
                        if (dist[h][k1 + 1] > val2 + w) {
                            dist[h][k1 + 1] = val2 + w;
                            st.insert({ dist[h][k1 + 1],{k1 + 1,h} });
                        }
                        if (dist[h][k1] > val + w) {
                            dist[h][k1] = val + w;
                            st.insert({ dist[h][k1],{k1,h} });
                        }
                    }
                    else {
                        if (dist[h][k1] > val + w) {
                            dist[h][k1] = val + w;
                            st.insert({ dist[h][k1],{k1,h} });
                        }
                    }
                }
            }
            else {
                if (a[u] == 0) {
                    if (dist[h][k1] > val + w) {
                        dist[h][k1] = val + w;
                        st.insert({ dist[h][k1],{k1,h} });
                    }
                }
                else {
                    if (a[u] == 2) {
                        if (dist[h][k1] > val + w) {
                            dist[h][k1] = val + w;
                            st.insert({ dist[h][k1],{k1,h} });
                        }
                    }
                    else {
                        if (dist[h][k1] > val + w) {
                            dist[h][k1] = val + w;
                            st.insert({ dist[h][k1],{k1,h} });
                        }
                    }
                }
            }
        }
    }
    double mn = oo;
    for (int i = 0; i <= k; ++i) {
        mn = min(mn, dist[h][i]);
    }
    if (mn == oo) {
        return -1;
    }
    return mn;
}

• 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