Submission #1154900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154900		tapilyoca	Cyberland (APIO23_cyberland)	C++20	0 / 100	62 ms	22336 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
// using double = long double;


class comp{
    public:

        bool operator()(pair<pair<double,ll>,ll> a, pair<pair<double,ll>,ll> b){
            if(a.first.first == b.first.first){
                if(a.second == b.second){
                    return a.first.second > b.first.second;
                }
                return a.second > b.second;
            }
            return a.first.first > b.first.first;
        }
};

double bleh(double weight, ll p){
    return weight/pow(2,p);
}

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) {
    
    vector<vector<pair<ll,ll>>> adj(N+1); // neigjbor, weight
    for(int i = 0; i < M; i++){
        ll a = x[i];
        ll b = y[i];
        ll w = c[i];
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }

    bool flag = 0;
    
    vector<bool> vis(N+1,0);
    vis[0] = 1;
    queue<ll> BFS_q;
    BFS_q.push(0);
    while(!BFS_q.empty()){
        ll at = BFS_q.front();
        BFS_q.pop();
        for(pair<ll,ll> p : adj[at]){
            ll node = p.first;
            if(vis[node]) continue;
            if(node == H){
                flag = 1;
                continue;
            }
            vis[node] = 1;

            BFS_q.push(node);
        }
    }

    if(not flag){
        return -1;
    }

    // dp-esque?
    // note that if K too big (over 30??) then we are within range lol
    K = min(100,K);

    vector<vector<double>> dists(N+1, vector<double>(K+1,1e18));
    dists[H][0] = 0;

    // djk
    // store: dist, k, node
    priority_queue<pair<pair<double,ll>,ll>, vector<pair<pair<double,ll>,ll>>, comp> pq;

    pq.push({{double(0),0},H});

    while(!pq.empty()){
        pair<pair<double,ll>,ll> front = pq.top();

        ll node = front.second;
        double curDist = front.first.first;
        ll k    = front.first.second;

        pq.pop();

        if(curDist > dists[node][k]){
            continue;
        }

        // if((node == 0 or arr[node] == 0) and vis[node]){
        //     return curDist;
        // }

        // cerr << "ON " << node << endl;
            
        for(pair<ll,ll> p : adj[node]){
            ll neighbor = p.first;
            if(!vis[neighbor]) continue;

            double weight = double(p.second);
            // very confusing since we're working backwards
            // since divide by two divides everything that we've traversed so far (from 0),
            // dividng by two will divide evertything that we WILL traverse from cyberland
            // so
            weight = bleh(weight,k);
            
            double newDist = curDist + weight;
            if(newDist < dists[neighbor][k]){
                dists[neighbor][k] = newDist;
                pq.push({{newDist,k},neighbor});
            }

            if(arr[node] == 2 and node != H and k < K){ // then we can also divide by two here
                newDist = curDist + (weight/double(2));
                if(newDist < dists[neighbor][k+1]){
                    dists[neighbor][k+1] = newDist;
                    pq.push({{newDist,k+1},neighbor});
                }            
            }
        }
    }
    assert(0);
}

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