Submission #1154749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154749		tapilyoca	Cyberland (APIO23_cyberland)	C++20	44 / 100	3098 ms	39448 KiB

cyberland

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

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


class comp{
    public:
        bool operator()(pair<pair<ll,ll>,ll> a, pair<pair<ll,ll>,ll> b){
            return a.first.first > b.first.first;
        }
};


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){
        cerr << "NOT EVEN CONNECTED " << endl;
        return -1;
    }

    cerr << "VIS: ";
    for(int i = 0; i < N; i++){
        cerr << vis[i] << " ";
    } cerr << endl;

    // for(int i = 0; i < N; i++){
    //     for(int j = 0; j < M; j++){
    //         cout << adj[i][j].first << " ";
    //     } cout << endl;
    // }

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

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

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

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


    // suppose closest node is node i...
    // then let its neighbor be j
    // arr[j] = 1 -> normal, check dist[i] + weight(i,j)
    // arr[j] = 0 -> this is a starting point, so return 
    // arr[j] = 2 -> weird, check (dist[i] + weight(i,j))/2 if k is not maxed out

    // normal djk afterwards?

    while(!pq.empty()){
        pair<pair<ld,ll>,ll> front = pq.top();
        cerr << "ON NODE " << front.second << " WITH ARR[NODE] = " << arr[front.second] << endl;
        pq.pop();

        ll node = front.second;
        ld curDist = front.first.first;
        ll k    = front.first.second;
            
        for(pair<ll,ll> p : adj[node]){
            ll neighbor = p.first;
            cerr << "CHECK NEIGHBOR " << neighbor << endl;
            if(!vis[neighbor]) continue;

            ld weight = ld(p.second);
            ld oldDist = dists[neighbor][k];

            if((arr[neighbor] != 2) or k == K or neighbor == 0){
                // normal case... so just do djk...
                if(curDist + weight < oldDist or oldDist == -1){
                    dists[neighbor][k] = curDist + weight;
                    pq.push({{dists[neighbor][k], k}, neighbor});
                }
            }

            // if(arr[neighbor] == 0 or neighbor == 0){
            //     cerr << "hi " << endl;
            //     return dists[neighbor][k];
            // }

            if(arr[neighbor] == 2 and k < K){
                if((curDist+weight)/ld(2) < oldDist or oldDist == -1){
                    dists[neighbor][++k] = (curDist + weight)/ld(2);
                    pq.push({{dists[neighbor][k], k}, neighbor});
                }
            }
        }
    }

    ld mn = 0;
    for(int i = 0; i < N; i++){
        
        if(i == H) continue;
        if(!vis[i]) continue;
        if(arr[i] != 0 and i != 0) continue;

        for(int j = 0; j < K; j++){
            if(dists[i][j] == -1) continue;
            
            if(!mn) mn = dists[i][j];
            else mn = min(mn, dists[i][j]);
        }
    }

    return mn;


    // assert(false); // should never run?
}

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