oj.uz

Submission #972681

# Submission time Handle Problem Language Result Execution time Memory
972681 2024-04-30T21:08:49 Z aykhn Cyberland (APIO23_cyberland) C++17
100 / 100
 1772 ms 15140 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MXN = 1e5 + 5;
 
int n, m, k, h;
vector<pair<int, double>> adj[MXN];
int arr[MXN];
double dist[MXN], ndist[MXN];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
vector<int> nodes;
 
void dijk(int s, int F)
{
    for (int i = 0; i < n; i++) ndist[i] = -1;
    for (int &x : nodes) ndist[x] = 0;
    if (F)
    {
        for (int i = 0; i < n; i++) 
        {
            if (arr[i] != 2) continue;
            for (pair<int, double> &v : adj[i])
            {
                if (v.first == h) continue;
                if (dist[v.first] == -1) continue;
                if (ndist[i] == -1) ndist[i] = (dist[v.first] + v.second) / 2;
                else ndist[i] = min(ndist[i], (dist[v.first] + v.second) / 2);
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (dist[i] != -1 && ndist[i] != -1) pq.push({min(dist[i], ndist[i]), i});
        else if (ndist[i] != -1) pq.push({ndist[i], i});
        else if (dist[i] != -1) pq.push({dist[i], i});
        
    }
    while (!pq.empty())
    {
        pair<double, int> f = pq.top();
        pq.pop();
        if (ndist[f.second] > f.first) continue;
        if (f.second == h) continue;
        for (pair<int, double> &v : adj[f.second])
        {
            if (ndist[v.first] == -1) 
            {
                ndist[v.first] = f.first + v.second;
                pq.push({ndist[v.first], v.first});
            }
            else if (ndist[v.first] > f.first + v.second) 
            {
                ndist[v.first] = f.first + v.second;
                pq.push({ndist[v.first], v.first});
            }
        }
    }
}
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR)
{
    n = N, m = M, k = K, h = H;
    k = min(k, 70);
    for (int i = 0; i < n; i++) adj[i].clear(), arr[i] = ARR[i], dist[i] = -1;
    nodes.clear();
    for (int i = 0; i < m; i++)
    {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    vector<int> u(n, 0);
    queue<int> q;
    u[0] = 1, q.push(0);
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        if (f == h) continue;
        for (pair<int, double> &v : adj[f])
        {
            if (u[v.first]) continue;
            u[v.first] = 1, q.push(v.first);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (u[i] && (!i || arr[i] == 0)) 
        {
            dist[i] = 0;
            nodes.push_back(i);
        }
        else dist[i] = -1;
    }
    double res = -1;
    for (int i = 0; i <= k; i++)
    {
        dijk(0, i);
        for (int i = 0; i < n; i++) 
        {
            if (dist[i] == -1) dist[i] = ndist[i];
            else if (ndist[i] != -1) dist[i] = min(dist[i], ndist[i]);
        }
        if (dist[h] != -1) 
        {
            if (res == -1) res = dist[h];
            else res = min(res, dist[h]);
        }
    }
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4700 KB Correct.
2 Correct 34 ms 4696 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 4976 KB Correct.
2 Correct 319 ms 4708 KB Correct.
3 Correct 306 ms 4700 KB Correct.
4 Correct 320 ms 4780 KB Correct.
5 Correct 316 ms 4972 KB Correct.
6 Correct 346 ms 5800 KB Correct.
7 Correct 469 ms 5884 KB Correct.
8 Correct 196 ms 6872 KB Correct.
9 Correct 115 ms 4640 KB Correct.
10 Correct 112 ms 4640 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 4692 KB Correct.
2 Correct 223 ms 4740 KB Correct.
3 Correct 198 ms 4728 KB Correct.
4 Correct 99 ms 4440 KB Correct.
5 Correct 101 ms 4620 KB Correct.
6 Correct 58 ms 5720 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9820 KB Correct.
2 Correct 111 ms 4680 KB Correct.
3 Correct 99 ms 4756 KB Correct.
4 Correct 109 ms 4964 KB Correct.
5 Correct 62 ms 4444 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4696 KB Correct.
2 Correct 141 ms 4700 KB Correct.
3 Correct 166 ms 4964 KB Correct.
4 Correct 207 ms 5940 KB Correct.
5 Correct 61 ms 4444 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4852 KB Correct.
2 Correct 87 ms 4852 KB Correct.
3 Correct 40 ms 11352 KB Correct.
4 Correct 89 ms 5720 KB Correct.
5 Correct 65 ms 4444 KB Correct.
6 Correct 104 ms 5124 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4696 KB Correct.
2 Correct 18 ms 4700 KB Correct.
3 Correct 723 ms 15140 KB Correct.
4 Correct 519 ms 7516 KB Correct.
5 Correct 327 ms 12236 KB Correct.
6 Correct 136 ms 10764 KB Correct.
7 Correct 516 ms 7252 KB Correct.
8 Correct 395 ms 4972 KB Correct.
9 Correct 92 ms 4912 KB Correct.
10 Correct 94 ms 4700 KB Correct.
11 Correct 326 ms 4984 KB Correct.
12 Correct 110 ms 4968 KB Correct.
13 Correct 98 ms 4772 KB Correct.
14 Correct 410 ms 10040 KB Correct.
15 Correct 428 ms 6224 KB Correct.
16 Correct 96 ms 4696 KB Correct.
17 Correct 120 ms 4900 KB Correct.
18 Correct 117 ms 5264 KB Correct.
19 Correct 363 ms 4748 KB Correct.
20 Correct 6 ms 4440 KB Correct.
21 Correct 8 ms 4700 KB Correct.
22 Correct 11 ms 5316 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 5292 KB Correct.
2 Correct 33 ms 4700 KB Correct.
3 Correct 1540 ms 15056 KB Correct.
4 Correct 569 ms 5456 KB Correct.
5 Correct 724 ms 12236 KB Correct.
6 Correct 285 ms 10956 KB Correct.
7 Correct 779 ms 9576 KB Correct.
8 Correct 483 ms 4788 KB Correct.
9 Correct 175 ms 4764 KB Correct.
10 Correct 186 ms 5012 KB Correct.
11 Correct 169 ms 4948 KB Correct.
12 Correct 203 ms 5888 KB Correct.
13 Correct 188 ms 5896 KB Correct.
14 Correct 1553 ms 12900 KB Correct.
15 Correct 1772 ms 12136 KB Correct.
16 Correct 830 ms 9044 KB Correct.
17 Correct 576 ms 7072 KB Correct.
18 Correct 181 ms 5716 KB Correct.
19 Correct 233 ms 5964 KB Correct.
20 Correct 214 ms 5716 KB Correct.
21 Correct 772 ms 7024 KB Correct.
22 Correct 11 ms 4700 KB Correct.
23 Correct 15 ms 4700 KB Correct.
24 Correct 22 ms 5468 KB Correct.