Submission #1081542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081542		Muhammet	Cyberland (APIO23_cyberland)	C++17	49 / 100	86 ms	48256 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"

using namespace std;

#define lb long double
#define ll long long

#define ff first
#define ss second

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
    vector <pair<ll, ll>> v[n+5];

    k = min(k,66);

    for(int i = 0; i < m; i++){
        v[x[i]].push_back({y[i],c[i]});
        v[y[i]].push_back({x[i],c[i]});
    }

    vector <vector<lb>> dis(n+1, vector<lb> (k+1,1e18));
    priority_queue <pair<lb,ll>> q;

    q.push({0,0});
    dis[0][0] = 0;
    while(!q.empty()){
        auto [w,x] = q.top();
        q.pop();
        w *= -1;
        if(w != dis[x][0]) continue;
        if(x == h) continue;
        for(auto [to,w1] : v[x]){
            if((dis[to][0] > dis[x][0] + w1) or (a[to] == 0 and dis[to][0] != 0)){
                dis[to][0] = dis[x][0] + w1;
                if(a[to] == 0) dis[to][0] = 0;
                q.push({-dis[to][0],to});
            }
        }
    }

    lb ans = 1e18;
    bool tr = 0;

    for(int i = 1; i < k; i++){
        q.push({0,0});
        for(int j = 0; j < n; j++){
            dis[j][i] = min(dis[j][i], dis[j][i-1]);
        }
        while(!q.empty()){
            auto [w,x] = q.top();
            q.pop();
            w *= -1;
            if(w != dis[x][i]) continue;
            if(x == h) continue;
            for(auto [to,w1] : v[x]){
                if(a[to] == 2){
                    lb w2 = w1;
                    if(dis[to][i] > (dis[x][i-1] + w2) / 2){
                        dis[to][i] = (dis[x][i-1] + w2) / 2;
                        q.push({-dis[to][i],to});
                    }
                }
                if((dis[to][i] > dis[x][i] + w1) or (a[to] == 0 and dis[to][i] != 0)){
                    dis[to][i] = dis[x][i] + w1;
                    if(a[to] == 0) dis[to][i] = 0;
                    q.push({-dis[to][i],to});
                }
            }
        }
    }

    for(int i = 0; i <= k; i++){
        ans = min(ans, dis[h][i]);
    }

    if(ans == 1e18) return -1;

    return ans;
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:44:10: warning: unused variable 'tr' [-Wunused-variable]
   44 |     bool tr = 0;
      |          ^~

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