oj.uz

Submission #890493

# Submission time Handle Problem Language Result Execution time Memory
890493 2023-12-21T10:29:38 Z abysmal Cyberland (APIO23_cyberland) C++17
100 / 100
 197 ms 67920 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 848 KB Correct.
2 Correct 24 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1744 KB Correct.
2 Correct 22 ms 2164 KB Correct.
3 Correct 20 ms 1780 KB Correct.
4 Correct 21 ms 1824 KB Correct.
5 Correct 21 ms 1840 KB Correct.
6 Correct 17 ms 4676 KB Correct.
7 Correct 28 ms 4424 KB Correct.
8 Correct 10 ms 7608 KB Correct.
9 Correct 22 ms 1396 KB Correct.
10 Correct 22 ms 1648 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1760 KB Correct.
2 Correct 20 ms 1816 KB Correct.
3 Correct 20 ms 1860 KB Correct.
4 Correct 21 ms 1372 KB Correct.
5 Correct 21 ms 1368 KB Correct.
6 Correct 4 ms 3272 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21852 KB Correct.
2 Correct 20 ms 1780 KB Correct.
3 Correct 19 ms 1844 KB Correct.
4 Correct 19 ms 1744 KB Correct.
5 Correct 22 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1676 KB Correct.
2 Correct 27 ms 1896 KB Correct.
3 Correct 23 ms 1788 KB Correct.
4 Correct 27 ms 4328 KB Correct.
5 Correct 21 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1856 KB Correct.
2 Correct 19 ms 2192 KB Correct.
3 Correct 42 ms 28720 KB Correct.
4 Correct 14 ms 3044 KB Correct.
5 Correct 22 ms 1384 KB Correct.
6 Correct 20 ms 1772 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1768 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 44 ms 26364 KB Correct.
4 Correct 42 ms 8720 KB Correct.
5 Correct 33 ms 16844 KB Correct.
6 Correct 24 ms 8516 KB Correct.
7 Correct 39 ms 7444 KB Correct.
8 Correct 40 ms 3072 KB Correct.
9 Correct 20 ms 1816 KB Correct.
10 Correct 20 ms 1708 KB Correct.
11 Correct 48 ms 2696 KB Correct.
12 Correct 22 ms 1808 KB Correct.
13 Correct 22 ms 1792 KB Correct.
14 Correct 38 ms 9480 KB Correct.
15 Correct 38 ms 4328 KB Correct.
16 Correct 27 ms 1844 KB Correct.
17 Correct 23 ms 1884 KB Correct.
18 Correct 23 ms 1900 KB Correct.
19 Correct 42 ms 2788 KB Correct.
20 Correct 3 ms 600 KB Correct.
21 Correct 3 ms 656 KB Correct.
22 Correct 3 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2008 KB Correct.
2 Correct 4 ms 1628 KB Correct.
3 Correct 75 ms 67920 KB Correct.
4 Correct 39 ms 4452 KB Correct.
5 Correct 40 ms 27720 KB Correct.
6 Correct 25 ms 11868 KB Correct.
7 Correct 42 ms 13144 KB Correct.
8 Correct 43 ms 2996 KB Correct.
9 Correct 24 ms 2100 KB Correct.
10 Correct 30 ms 1960 KB Correct.
11 Correct 197 ms 1776 KB Correct.
12 Correct 27 ms 2100 KB Correct.
13 Correct 24 ms 2060 KB Correct.
14 Correct 48 ms 28244 KB Correct.
15 Correct 51 ms 34872 KB Correct.
16 Correct 41 ms 12744 KB Correct.
17 Correct 41 ms 4308 KB Correct.
18 Correct 25 ms 2144 KB Correct.
19 Correct 30 ms 2196 KB Correct.
20 Correct 26 ms 2116 KB Correct.
21 Correct 55 ms 3116 KB Correct.
22 Correct 3 ms 604 KB Correct.
23 Correct 3 ms 1016 KB Correct.
24 Correct 3 ms 1372 KB Correct.