제출 #890493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890493		abysmal	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	197 ms	67920 KiB

cyberland

#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<math.h>
#include<assert.h>

using namespace std;

const double PI = (double) atan(1.0) * 4;
const int64_t INF = (int64_t) 1e18 + 777;
const int64_t mINF = (int64_t) 1e9 + 777;
const int64_t offset = (int64_t) 1e6 + 777;
const int64_t MOD = 1e9 + 7;
const int nbit = 11;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};

struct Edge
{
    int v; int w;

    Edge(int v_, int w_) : v(v_), w(w_) {}
};

int find(int t1, vector<int>& link)
{
    while(t1 != link[t1]) t1 = link[t1];
    return t1;
}

void unite(int t1, int t2, vector<int>& link, vector<int>& size)
{
    t1 = find(t1, link); t2 = find(t2, link);
    if(t1 == t2) return;
    if(size[t1] < size[t2]) swap(t1, t2);
    size[t1] += size[t2];
    link[t2] = t1;
}

struct Node
{
    int u;
    double w;
    int c;

    Node(int u_, double w_, int c_) : u(u_), w(w_), c(c_) {}

    bool operator < (const Node& o) const
    {
        if(w == o.w) return c > o.c;
        return w > o.w;
    }
};

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> weight, vector<int> a)
{
    vector<vector<Edge> > adj;
    vector<int> link(n);
    vector<int> size(n, 1);
    for(int i = 0; i < n; i++)
    {
        link[i] = i;
    }

    adj.resize(n);
    for(int i = 0; i < m; i++)
    {
        if(x[i] != h && y[i] != h) unite(x[i], y[i], link, size);
        adj[x[i]].emplace_back(y[i], weight[i]);
        adj[y[i]].emplace_back(x[i], weight[i]);
    }

    k = min(k, 70 - 1);
    vector<double> pow(k + 1, 1.0);
    for(int i = 1; i <= k; i++)
    {
        pow[i] = pow[i - 1] / 2.0;
    }

    a[0] = 0; int st = 0;
    priority_queue<Node> pq;
    vector<vector<double> > dis(k + 1, vector<double>(n, INF));
    dis[0][h] = 0; pq.push(Node(h, 0, 0));
    while(!pq.empty())
    {
        Node xx = pq.top();
        pq.pop();

        int u = xx.u; double w = xx.w; int c = xx.c;
        if(dis[c][u] != w) continue;
        if(a[u] == 0) return dis[c][u];

        for(int i = 0; i < (int) adj[u].size(); i++)
        {
            int v = adj[u][i].v;
            int ew = adj[u][i].w;
            if(find(v, link) != find(st, link)) continue;

            if(dis[c][v] > dis[c][u] + ew * pow[c])
            {
                dis[c][v] = dis[c][u] + ew * pow[c];
                pq.push(Node(v, dis[c][v], c));
            }

            if(c != k && a[u] == 2 && dis[c + 1][v] > dis[c][u] + ew * pow[c + 1])
            {
                dis[c + 1][v] = dis[c][u] + ew * pow[c + 1];
                pq.push(Node(v, dis[c + 1][v], c + 1));
            }
        }
    }

    return -1;
}

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