Submission #837904

#	Time	Username	Problem	Language	Result	Execution time	Memory
837904		beaconmc	Cyberland (APIO23_cyberland)	C++17	97 / 100	3047 ms	80872 KiB

cyberland

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "cyberland.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef double ll;

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(int i=x; i<y; i++)
#define FORNEG(i, x, y) for(int i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mp make_pair
#define fir first
#define sec second


vector<pair<long long,ll>> edges[100001];
ll dists[100001][71];



double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    FOR(i,0,N+1) FOR(j,0,71) dists[i][j] = 1000000000000000;
    FOR(i,0,N+1) edges[i].clear();
    FOR(i,0,M){
        edges[x[i]].push_back(mp(y[i], c[i]));
        edges[y[i]].push_back(mp(x[i], c[i]));
    }


    priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> p;

    FOR(i,0,N){
        if (i==0){
            dists[i][0] =  0;
            p.push({0, (ll) i, 0});
        }
    }


    while (p.size()){
        ll dist = p.top()[0];
        long long node = (long long) p.top()[1];
        long long times = (long long) p.top()[2];
        p.pop();
        if (node==H) continue;

        if (dists[node][times] < dist) continue;

        

        for (auto&i : edges[node]){
            if (arr[i.fir]==0){
                if (dists[i.fir][times] > 0){
                    dists[i.fir][times] = 0;
                    p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
                }
                continue;
            }

            if (dists[i.fir][times] > dists[node][times] + i.sec){
                dists[i.fir][times] = dists[node][times] + i.sec;
                p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
            }
            if (arr[i.fir] == 2){
                if (times == K || times == 70) continue;
                ll newdist = (dists[node][times] + i.sec)/2;

                if (dists[i.fir][times+1] > newdist){
                    dists[i.fir][times+1] = newdist;
                    p.push({dists[i.fir][times+1],(ll) i.fir, (ll) times+1});
                }
            }

        }
    }
    ll ans = 1000000000000000;

    FOR(i,0,min(K+1, 70)){
        ans = min(ans, dists[H][i]);
    }
    if (ans==1000000000000000) 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