Submission #1080803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080803		Muhammet	Cyberland (APIO23_cyberland)	C++17	97 / 100	3056 ms	112200 KiB

cyberland

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

using namespace std;

#define ll long double

#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<long long, long long>> v[n+5];

    k = min(k,70);

    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]});
    }
    priority_queue <pair<ll,pair<long long,long long>>> q;
    q.push({0,{0,0}});
    vector <vector<ll>> dis(n+1, vector<ll> (k+1,1e18)), vis(n+1, vector<ll> (k+1,1e18));
    dis[0][0] = 0;
    vis[0][0] = 0;
    while(!q.empty()){
        auto [w,x] = q.top();
        q.pop();
        vis[x.ff][x.ss] = 1;
        if(-w != dis[x.ff][x.ss]) continue;
        if(x.ff == h) continue;
        for(auto [to,w1] : v[x.ff]){
            if(a[to] == 2 and x.ss < k){
                ll w2 = w1;
                if(vis[to][x.ss+1] == 0 or (dis[x.ff][x.ss] + w2) / 2 < dis[to][x.ss+1]){
                    dis[to][x.ss+1] = (dis[x.ff][x.ss] + w2) / 2;
                    q.push({-dis[to][x.ss+1],{to,x.ss+1}});
                }
            }
            if((dis[to][x.ss] > dis[x.ff][x.ss] + w1) or (a[to] == 0 and dis[to][x.ss] != 0) or (vis[to][x.ss] == 0)){
                dis[to][x.ss] = dis[x.ff][x.ss] + w1;
                if(a[to] == 0) dis[to][x.ss] = 0;
                q.push({-dis[to][x.ss],{to,x.ss}});
            }
        }
    }

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

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

    return ans;
}

• 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