Submission #1228137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228137		Dzadzo	Cyberland (APIO23_cyberland)	C++20	68 / 100	3098 ms	82284 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 200000
using namespace std;

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


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) {
    vvp adj(n);
    for (int i=0;i<m;i++) {
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i],c[i]});
    }


    vb visited(n);
    bool res=false;
    function<void(int)> dfs = [&](int v) {
        // cout<<v<<'\n';
        if (v==h) {
            res=true;
            return;
        }
        visited[v]=true;
        for (auto &[to,w]:adj[v]) {
            if (!visited[to]) {
                dfs(to);
            }
        }
    };
    dfs(0);
    if (!res)return -1;

    vector <vector <double>> dist(n, vector<double>(76, INF));
    dist[0][0]=0;

    priority_queue < pair < pair <double,int>,int>   ,  vector  < pair <pair <double,int>,int> >,greater< pair<pair <double,int>,int> >>  pq;


    pq.push({{dist[0][0],0},0});


    for (int i=1;i<n;i++)if (!arr[i] && visited[i]) {

        dist[i][0]=0;
        pq.push({{dist[i][0],0},i});
    }

    while (!pq.empty()) {
        int v=pq.top().S;
        int k=pq.top().F.S;
        int dis=pq.top().F.F;
        pq.pop();
        if ( dis - dist[v][k] > 0.0001 || dis-dist[v][k]< 0.0001 ) {
            // cout<<v<<" "<<k<<" "<<dist[v][k]<<'\n';
            if (v==h)continue;
            for (auto &[to,w]:adj[v]) {
                if (dist[to][k] > dist[v][k] + w) {
                    dist[to][k]=dist[v][k] + w;
                    pq.push({{dist[to][k],k},to});
                }

                if (arr[to]==2 && k<75) {
                    if (dist[to][k+1] > (dist[v][k] + w)/2) {
                        dist[to][k+1]=(dist[v][k] + w)/2;
                        pq.push({{dist[to][k+1],k+1},to});
                    }
                }
            }
        }
    }
    double ans=dist[h][0];
    // cout<<h<<'\n';
    for (int i=1;i<=min(K,75);i++)ans=min(ans,dist[h][i]);
    return ans;
}
// //
// int main() {
//     // int n,m,k,h;
//     // cin>>n>>m>>k>>h;
//     // vi arr;
//     // for (int i=0;i<n;i++) {
//     //     int x;
//     //     cin>>x;
//     //     arr.pb(x);
//     // }
//     // vi X,Y,C;
//     // for (int i=0;i<m;i++) {
//     //     int x,y,c;
//     //     cin>>x>>y>>c;
//     //     X.pb(x);
//     //     Y.pb(y);
//     //     C.pb(c);
//     // }
//     // cout<<solve(n,m,k,h,X,Y,C,arr);
//     cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
// }


/*

3 2 30
1
1 1 2
1 2 23211
0 1 9991
*/

• 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: 0 / 29
• Subtask 8: 0 / 3