Submission #764295

#	Time	Username	Problem	Language	Result	Execution time	Memory
764295		PoonYaPat	Cyberland (APIO23_cyberland)	C++17	100 / 100	426 ms	263196 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair<int,ld> pii;

struct NN {
    ld d;
    int node,half;
    bool zer;
    bool operator < (const NN &o) const {return d>o.d;}
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    int n=N,m=M,k=min(K,70),st=H;
    vector<pii> adj[n];
    ld dis[n][k+5][2];
    bool vis[n][k+5][2];
    for (int i=0; i<n; ++i) for (int j=0; j<=k; ++j) dis[i][j][0]=DBL_MAX, dis[i][j][1]=DBL_MAX, vis[i][j][0]=false, vis[i][j][1]=false;

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

    priority_queue<NN> q;
    dis[st][0][0]=0;
    q.push({dis[st][0][0],st,0,0});
    bool bef=false;

    while (!q.empty()) {
        int node=q.top().node, half=q.top().half;
        bool zer=q.top().zer;
        q.pop();

        if (vis[node][half][zer]) continue;
        vis[node][half][zer]=true;

        if (node==st) {
            if (!bef) bef=true;
            else continue;
        }
        if (node==0) return (double)(dis[node][half][zer]);

        for (auto s : adj[node]) {
            int des=s.first;
            ld w=s.second;

            if (zer==true) w=0;
            else w=w/pow(2,half);

            if (arr[node]==1) {
                if (dis[des][half][zer]>dis[node][half][zer]+w) {
                    dis[des][half][zer]=dis[node][half][zer]+w;
                    q.push({dis[des][half][zer],des,half,zer});
                }
            } else if (arr[node]==0) {
                if (dis[des][half][true]>dis[node][half][zer]) {
                    dis[des][half][true]=dis[node][half][zer];
                    q.push({dis[des][half][true],des,half,true});
                }
            } else {
                //don't use
                if (dis[des][half][zer]>dis[node][half][zer]+w) {
                    dis[des][half][zer]=dis[node][half][zer]+w;
                    q.push({dis[des][half][zer],des,half,zer});
                }

                //use
                if (half<k) {
                    if (dis[des][half+1][zer]>dis[node][half][zer]+w/2.0) {
                        dis[des][half+1][zer]=dis[node][half][zer]+w/2.0;
                        q.push({dis[des][half+1][zer],des,half+1,zer});
                    }
                }
            }

        }
    }
    return -1;
}

• 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: 3 / 3