Submission #984985

#	Time	Username	Problem	Language	Result	Execution time	Memory
984985		IUA_Hasin	Cyberland (APIO23_cyberland)	C++17	0 / 100	22 ms	34260 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
 
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define ll                                  long long
#define ld                                  long double
 
using namespace std; 


const ll M = 3e5+5;
const ll INF = 5e16+69;

vector<ll> ind0;
vector<pair<ll, ll>> extra[M];
vector<pair<ll, ll>> graph[M];
vector<ll> dist(M, INF);
ll vis[M];

void dijkstra(ll source){
    set<pair<ll, ll>> s;
    s.insert({0, source});
    dist[source] = 0;

    while(s.size()>0){
        auto node = *s.begin();
        ll v = node.second;
        ll v_dist = node.first;
        s.erase(s.begin());
        if(vis[v]==0){
            for(auto child : graph[v]){
                ll v2 = child.first;
                ll wt = child.second;
                if((dist[v]+wt)<(dist[v2])){
                    dist[v2] = dist[v]+wt;
                    s.insert({dist[v2], v2});
                }
            }
            vis[v] = 1;
        }
    }
    
}

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) {
    ll last0 = 0;
    ll last2 = -1;
    for(int i=1; i<H; i++){
        if(arr[i]==0){
            last0 = i;
        }
        if(arr[i]==2){
            last2 = i;
        }
    }

    //cout << last0 << " " << last2 << endl;

    ll pref[N+1];
    pref[0] = 0;
    for(int i=0; i<N; i++){
        pref[i+1] = pref[i]+c[i];
    }

    if(last2<last0){
        ll ans = pref[H]-pref[last0];
        //cout << pref[H+1] << " " << c[last0+1] << endl;
        return ans;
    } else {
        ld before = pref[last2]-pref[last0];
        //cout << (ld)before << endl;
        if(K>0){
            before = before/2;
        }
        //cout<< (ld)before << endl;
        ll K2 = K-1;
        ll wt = c[last2-1];
        //cout<<(ld)wt<<endl;
        while(K2--){
            ld temp = (before+2*wt)/2;
            //cout << temp << endl;
            if(temp<before){
                before = temp;
            } else {
                break;
            }
        }
        ld after = pref[H]-pref[last2];
        //cout << (ld)after << endl;
        ld ans = before+after;
        return ans;
    }

}   

Compilation message (stderr)

cyberland.cpp: In function 'void dijkstra(long long int)':
cyberland.cpp:30:12: warning: unused variable 'v_dist' [-Wunused-variable]
   30 |         ll v_dist = node.first;
      |            ^~~~~~

• 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