Submission #896789

#	Time	Username	Problem	Language	Result	Execution time	Memory
896789		NotLinux	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#include <boost/rational.hpp>

using namespace std;

typedef long long ll;
typedef boost::rational < ll > db;
typedef pair < db , pair < int , int > > VAR;

const int MAXK = 31;
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) {
    // cout << "starting " << endl;
    bitset < 31 > vis[n];
    fill(vis , vis + n , 0);
 
    vector < pair < int , int > > graph[n];
    for(int i = 0;i<m;i++){
        graph[x[i]].push_back({y[i] , c[i]});
        graph[y[i]].push_back({x[i] , c[i]});
    }
 
    priority_queue < VAR > pq;//dist , node , how much k used
    pq.push({0L,{0,0}});
 
    function < void (int) > dfs = [&](int cur){
        if(vis[cur] == 1 or cur == h)return;
        vis[cur] = 1;
        if(arr[cur] == 0){
            pq.push({0L,{cur,0}});
            // cout << "pushed : " << cur << endl;
        }
        for(auto itr : graph[cur]){
            dfs(itr.first);
        }
    };
    // cout << "flag0 " << endl;
    dfs(0);
    fill(vis , vis + n , 0);
 
    db ans = 1L;
    // cout << "flag1 " << endl;
    while(pq.size()){
        VAR tmp = pq.top();
        pq.pop();
        if(vis[tmp.second.first][tmp.second.second])continue;
        vis[tmp.second.first][tmp.second.second] = 1;
        // cout << "pq : " << tmp.first.first << " / " << tmp.first.second << " , " << tmp.second.first << " " << tmp.second.second << endl;
        if(tmp.second.first == h){
            // cout << "flag1.1" << endl;
            if(ans == 1 or ans < tmp.first){
                ans = tmp.first;
            }
            // cout << "flag1.2" << endl; 
        }
        else{
            // cout << "flag2.1" << endl;
            for(auto itr : graph[tmp.second.first]){
                if(arr[tmp.second.first] == 2 and tmp.second.second < k){
                    pq.push({tmp.first / 2L - itr.second , {itr.first , tmp.second.second+1}});
                }
                pq.push({tmp.first - itr.second , {itr.first , tmp.second.second}});
            }
            // cout << "flag2.2" << endl;
        }
    }
    // cout << "flag3 " << endl;
    return (double)(-ans).numerator() / (double)(-ans).denominator();
}

Compilation message (stderr)

cyberland.cpp:3:10: fatal error: boost/rational.hpp: No such file or directory
    3 | #include <boost/rational.hpp>
      |          ^~~~~~~~~~~~~~~~~~~~
compilation terminated.