oj.uz

Submission #750264

# Submission time Handle Problem Language Result Execution time Memory
750264 2023-05-29T08:50:02 Z blue Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 30140 KB 
#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pid = pair<int, double>;

#define sz(x) int(x.size())






int N, M, K;
int H;
vi x, y, c, arr;

vector<pid>* edge;

//i = not halved yet, i + N = halved

vi reachable;


vector<double> dijkstra(vector<double> dist)
{
    priority_queue< pair<double, int> > tbv;
    for(int i = 0; i < 2*N; i++)
    {
        tbv.push({-dist[i], i});
    }

    while(!tbv.empty())
    {
        int u = tbv.top().second;

        if(dist[u] < -tbv.top().first)
        {
            tbv.pop();
            continue;
        }
        else
        {    
            tbv.pop();
        }


        if(u == H || u == H+N)
            continue;

        for(pid vp : edge[u])
        {
            int v = vp.first;
            if(dist[v] <= dist[u] + vp.second)
                continue;

            // tbv.erase({dist[v], v});

            dist[v] = dist[u] + vp.second;

            tbv.push({-dist[v], v});
        }
    } 

    return dist;
}







double solve(int N_, int M_, int K_, int H_, vi x_, vi y_, vi c_, vi arr_) 
{
    N = N_;
    M = M_;
    K = K_;
    H = H_;

    x = x_;
    y = y_;
    c = c_;
    arr = arr_;

    edge = new vector<pid>[2*N];

    for(int j = 0; j < M; j++)
    {
        edge[x[j]].push_back({y[j], c[j]});
        edge[y[j]].push_back({x[j], c[j]});

        edge[N+x[j]].push_back({y[j], c[j]});
        edge[N+y[j]].push_back({x[j], c[j]});
    }



    vector<double> dist(2*N, double(2'000'000'000) * double(M + 1));

    dist[0] = 0;

    reachable = vi(N, 1);

    dist = dijkstra(dist);

    for(int i = 0; i < N; i++)
        if(arr[i] == 0 && dist[i] < double(1'500'000'000) * double(M + 1))
            dist[i] = double(0);


    for(int i = 0; i < N; i++)
        if(dist[i] >= double(1'500'000'000) * double(M+1))
            reachable[i] = 0;



    K = min(K, 70);

    // K = 0;
    for(int k = 1; k <= K; k++)
    {
        dist = dijkstra(dist);

        for(int i = 0; i < N; i++)
        {
            if(arr[i] == 2)
            {
                dist[i+N] = dist[i] / double(2);
                dist[i] = double(2'000'000'000) * double(M + 1);
            }
        }

        for(int i = 0; i < N; i++)
            if(!reachable[i])
                dist[i] = dist[i+N] = double(2'000'000'000) * double(M + 1);
    } 

    dist = dijkstra(dist);
    for(int i = 0; i < N; i++)
            if(!reachable[i])
                dist[i] = double(2'000'000'000) * double(M + 1);


    if(!reachable[H])
        return -1;
    else
        return dist[H];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3004 KB Correct.
2 Correct 94 ms 2912 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 7044 KB Correct.
2 Correct 334 ms 8468 KB Correct.
3 Correct 309 ms 7868 KB Correct.
4 Correct 335 ms 8244 KB Correct.
5 Correct 325 ms 8212 KB Correct.
6 Correct 389 ms 7104 KB Correct.
7 Correct 514 ms 9408 KB Correct.
8 Correct 245 ms 6568 KB Correct.
9 Correct 202 ms 7892 KB Correct.
10 Correct 199 ms 7752 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 7968 KB Correct.
2 Correct 312 ms 7888 KB Correct.
3 Correct 301 ms 7496 KB Correct.
4 Correct 222 ms 7992 KB Correct.
5 Correct 218 ms 7980 KB Correct.
6 Correct 84 ms 2768 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 17284 KB Correct.
2 Correct 388 ms 7704 KB Correct.
3 Correct 349 ms 7096 KB Correct.
4 Correct 364 ms 7400 KB Correct.
5 Correct 247 ms 7416 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 7116 KB Correct.
2 Correct 306 ms 8156 KB Correct.
3 Correct 307 ms 7864 KB Correct.
4 Correct 363 ms 7316 KB Correct.
5 Correct 219 ms 7116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 7688 KB Correct.
2 Correct 287 ms 7096 KB Correct.
3 Correct 1209 ms 25096 KB Correct.
4 Correct 351 ms 5916 KB Correct.
5 Correct 254 ms 7632 KB Correct.
6 Correct 355 ms 7460 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 7496 KB Correct.
2 Correct 42 ms 1364 KB Correct.
3 Correct 1484 ms 30008 KB Correct.
4 Correct 954 ms 18600 KB Correct.
5 Correct 983 ms 17944 KB Correct.
6 Correct 295 ms 12544 KB Correct.
7 Correct 831 ms 16764 KB Correct.
8 Correct 586 ms 15420 KB Correct.
9 Correct 346 ms 7296 KB Correct.
10 Correct 345 ms 7244 KB Correct.
11 Correct 529 ms 15344 KB Correct.
12 Correct 396 ms 8016 KB Correct.
13 Correct 369 ms 7664 KB Correct.
14 Correct 625 ms 18428 KB Correct.
15 Correct 608 ms 15236 KB Correct.
16 Correct 372 ms 7752 KB Correct.
17 Correct 399 ms 8112 KB Correct.
18 Correct 393 ms 7864 KB Correct.
19 Correct 948 ms 15196 KB Correct.
20 Correct 23 ms 972 KB Correct.
21 Correct 35 ms 936 KB Correct.
22 Correct 17 ms 1620 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 7508 KB Correct.
2 Correct 81 ms 1288 KB Correct.
3 Correct 2182 ms 30140 KB Correct.
4 Correct 789 ms 15824 KB Correct.
5 Correct 1892 ms 17976 KB Correct.
6 Correct 536 ms 12484 KB Correct.
7 Correct 1113 ms 20784 KB Correct.
8 Correct 739 ms 15376 KB Correct.
9 Correct 733 ms 7220 KB Correct.
10 Correct 781 ms 7208 KB Correct.
11 Correct 483 ms 12396 KB Correct.
12 Correct 892 ms 8000 KB Correct.
13 Correct 815 ms 7616 KB Correct.
14 Correct 2484 ms 17536 KB Correct.
15 Execution timed out 3064 ms 19956 KB Time limit exceeded
16 Halted 0 ms 0 KB -