oj.uz

Submission #972682

# Submission time Handle Problem Language Result Execution time Memory
972682 2024-04-30T21:12:14 Z TheSahib Cyberland (APIO23_cyberland) C++17
100 / 100
 1780 ms 15028 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 4688 KB Correct.
2 Correct 30 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 4984 KB Correct.
2 Correct 331 ms 4692 KB Correct.
3 Correct 312 ms 5012 KB Correct.
4 Correct 319 ms 4748 KB Correct.
5 Correct 314 ms 4752 KB Correct.
6 Correct 370 ms 5832 KB Correct.
7 Correct 463 ms 5836 KB Correct.
8 Correct 195 ms 6868 KB Correct.
9 Correct 121 ms 4640 KB Correct.
10 Correct 113 ms 4624 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4696 KB Correct.
2 Correct 218 ms 4696 KB Correct.
3 Correct 199 ms 4972 KB Correct.
4 Correct 102 ms 4444 KB Correct.
5 Correct 100 ms 4628 KB Correct.
6 Correct 55 ms 5720 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10112 KB Correct.
2 Correct 111 ms 4700 KB Correct.
3 Correct 99 ms 4696 KB Correct.
4 Correct 105 ms 4696 KB Correct.
5 Correct 66 ms 4628 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4732 KB Correct.
2 Correct 142 ms 4700 KB Correct.
3 Correct 162 ms 4696 KB Correct.
4 Correct 212 ms 6004 KB Correct.
5 Correct 61 ms 4444 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 4780 KB Correct.
2 Correct 90 ms 4696 KB Correct.
3 Correct 44 ms 11600 KB Correct.
4 Correct 91 ms 5724 KB Correct.
5 Correct 61 ms 4624 KB Correct.
6 Correct 103 ms 4840 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4816 KB Correct.
2 Correct 17 ms 4696 KB Correct.
3 Correct 772 ms 15028 KB Correct.
4 Correct 520 ms 7304 KB Correct.
5 Correct 348 ms 12232 KB Correct.
6 Correct 144 ms 10844 KB Correct.
7 Correct 517 ms 7320 KB Correct.
8 Correct 395 ms 5180 KB Correct.
9 Correct 98 ms 4952 KB Correct.
10 Correct 99 ms 5208 KB Correct.
11 Correct 325 ms 4968 KB Correct.
12 Correct 105 ms 5000 KB Correct.
13 Correct 104 ms 5112 KB Correct.
14 Correct 407 ms 9932 KB Correct.
15 Correct 428 ms 6192 KB Correct.
16 Correct 105 ms 4836 KB Correct.
17 Correct 118 ms 4864 KB Correct.
18 Correct 119 ms 5036 KB Correct.
19 Correct 372 ms 5000 KB Correct.
20 Correct 7 ms 4444 KB Correct.
21 Correct 9 ms 4676 KB Correct.
22 Correct 12 ms 5208 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 4716 KB Correct.
2 Correct 36 ms 4700 KB Correct.
3 Correct 1542 ms 14988 KB Correct.
4 Correct 589 ms 5824 KB Correct.
5 Correct 745 ms 12232 KB Correct.
6 Correct 285 ms 10840 KB Correct.
7 Correct 779 ms 9572 KB Correct.
8 Correct 488 ms 4992 KB Correct.
9 Correct 181 ms 4952 KB Correct.
10 Correct 183 ms 4704 KB Correct.
11 Correct 168 ms 4632 KB Correct.
12 Correct 202 ms 4696 KB Correct.
13 Correct 191 ms 4700 KB Correct.
14 Correct 1543 ms 10964 KB Correct.
15 Correct 1780 ms 10212 KB Correct.
16 Correct 827 ms 6992 KB Correct.
17 Correct 577 ms 5072 KB Correct.
18 Correct 181 ms 5020 KB Correct.
19 Correct 238 ms 5048 KB Correct.
20 Correct 215 ms 4748 KB Correct.
21 Correct 783 ms 4792 KB Correct.
22 Correct 11 ms 4440 KB Correct.
23 Correct 15 ms 4700 KB Correct.
24 Correct 22 ms 5320 KB Correct.