제출 #753474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753474		quanlt206	사이버랜드 (APIO23_cyberland)	C++17	97 / 100	2163 ms	126928 KiB

cyberland

#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 1e5 + 7;

vector<pii> v[N];

double d[N][150];

bool p[N];

int a[N];

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) {
    REP(i, 0, n) v[i].clear();
    REP(i, 0, n) a[i] = arr[i];
    REP(i, 0, m) {
        v[x[i]].push_back({y[i], c[i]});
        v[y[i]].push_back({x[i], c[i]});
//        cout<<x[i]<<" "<<y[i]<<" "<<c[i]<<"\n";
    }
    #define pdii pair<ld, pii>
    priority_queue<pdii, vector<pdii>, greater<pdii>> pq;
    FOR(i, 0, n) p[i] = true;
    p[0] = false;
    queue<int> qu;
    qu.push(0);
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for (auto y : v[x])
            if (p[y.X] && y.X != H) {
                p[y.X] = false;
                qu.push(y.X);
            }
    }
    k = min(k, 60);
    FOR(i, 0, n)
        FOR(j, 0, k) d[i][j] = 1e15;
    d[0][0] = 0;
    pq.push({0, {0, 0}});
    REP(i, 0, n)
        if (a[i] == 0 && !p[i]) {
            pq.push({0, {i, 0}});
            d[i][0] = 0;
        }
    while (!pq.empty()) {
        pdii tmp = pq.top();
        pq.pop();
        double w = tmp.X;
        int x = tmp.Y.X, t = tmp.Y.Y;
        if (w > d[x][t]) continue;
//        cout<<x<<" "<<t<<" "<<w<<"\n";
        for (auto y : v[x]) {
            double new_w = w + y.Y;
            if (minimize(d[y.X][t], new_w) && y.X != H) pq.push({d[y.X][t], {y.X, t}});
            if (t + 1 <= k && a[y.X] == 2 && minimize(d[y.X][t + 1], new_w / 2.0) && y.X != H)
                pq.push({d[y.X][t + 1], {y.X, t + 1}});
        }
    }
    double res = 1e18;
    FOR(j, 0, k) minimize(res, d[H][j]);
    if (res > 1e14) return -1;
    return res;
}

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