oj.uz

Submission #771944

# Submission time Handle Problem Language Result Execution time Memory
771944 2023-07-03T12:31:55 Z Tenis0206 Cyberland (APIO23_cyberland) C++17
97 / 100
 820 ms 72820 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int kmax = 60;
const long long oo = LLONG_MAX;

int n,m,k,f;

int tip[nmax + 5];

double d[nmax + 5][kmax + 5];
bool sel[nmax + 5][kmax + 5];

vector<pair<int,int>> G[nmax + 5];

vector<int> l;

typedef pair<pair<int,double>,int> pi;

void add_zero(int nod)
{
    sel[nod][0] = true;
    if(tip[nod]==0)
    {
        l.push_back(nod);
    }
    if(nod==f)
    {
        return;
    }
    for(auto it : G[nod])
    {
        if(sel[it.first][0])
        {
            continue;
        }
        add_zero(it.first);
    }
}

void Dijkstra()
{
    priority_queue <pi,vector<pi>,greater<pi>> h;
    for(int i=0;i<n;i++)
    {
        for(int p=0;p<=min(kmax,k);p++)
        {
            d[i][p] = oo;
            sel[i][p] = false;
        }
    }
    d[0][0] = 0;
    h.push({{0,0},0});
    l.clear();
    add_zero(0);
    if(!sel[f][0])
    {
        d[f][0] = -1;
        return;
    }
    for(int i=0;i<n;i++)
    {
        sel[i][0] = false;
    }
    for(auto it : l)
    {
        d[it][0] = 0;
        h.push({{0,0},it});
    }
    while(!h.empty())
    {
        while(!h.empty() && sel[h.top().second][h.top().first.first])
        {
            h.pop();
        }
        if(h.empty())
        {
            return;
        }
        int nod = h.top().second;
        int nr = h.top().first.first;
        h.pop();
        sel[nod][nr] = true;
        if(nod==f)
        {
            continue;
        }
        for(auto it : G[nod])
        {
            double new_t = d[nod][nr] + it.second;
            if(tip[it.first]==0)
            {
                continue;
            }
            if(new_t < d[it.first][nr])
            {
                d[it.first][nr] = new_t;
                h.push({{nr,d[it.first][nr]},it.first});
            }
            if(tip[it.first]==2 && nr < min(kmax,k))
            {
                if(new_t * 0.5 < d[it.first][nr + 1])
                {
                    d[it.first][nr+1] = new_t * 0.5;
                    h.push({{nr+1,d[it.first][nr+1]},it.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, f = H;
    for(int i=0;i<m;i++)
    {
        G[x[i]].push_back({y[i],c[i]});
        G[y[i]].push_back({x[i],c[i]});
    }
    for(int i=0;i<n;i++)
    {
        tip[i] = arr[i];
    }
    Dijkstra();
    for(int i=0;i<n;i++)
    {
        G[i].clear();
    }
    double rez = oo;
    for(int p=0;p<=min(kmax,k);p++)
    {
        rez = min(rez, d[f][p]);
    }
    return rez;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2820 KB Correct.
2 Correct 16 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3412 KB Correct.
2 Correct 24 ms 3336 KB Correct.
3 Correct 22 ms 3400 KB Correct.
4 Correct 23 ms 3412 KB Correct.
5 Correct 23 ms 3412 KB Correct.
6 Correct 22 ms 8996 KB Correct.
7 Correct 28 ms 8956 KB Correct.
8 Correct 17 ms 15428 KB Correct.
9 Correct 21 ms 2800 KB Correct.
10 Correct 21 ms 2800 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3392 KB Correct.
2 Correct 29 ms 3404 KB Correct.
3 Correct 22 ms 3476 KB Correct.
4 Correct 23 ms 2772 KB Correct.
5 Correct 23 ms 2792 KB Correct.
6 Correct 8 ms 8148 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 40996 KB Correct.
2 Correct 75 ms 3440 KB Correct.
3 Correct 69 ms 3712 KB Correct.
4 Correct 71 ms 3688 KB Correct.
5 Correct 47 ms 3080 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3412 KB Correct.
2 Correct 22 ms 3544 KB Correct.
3 Correct 23 ms 3500 KB Correct.
4 Correct 24 ms 9644 KB Correct.
5 Correct 19 ms 2992 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3444 KB Correct.
2 Correct 18 ms 3464 KB Correct.
3 Correct 48 ms 51420 KB Correct.
4 Correct 16 ms 7580 KB Correct.
5 Correct 23 ms 2788 KB Correct.
6 Correct 22 ms 3540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3400 KB Correct.
2 Correct 15 ms 3884 KB Correct.
3 Correct 641 ms 65808 KB Correct.
4 Correct 267 ms 18068 KB Correct.
5 Correct 317 ms 31408 KB Correct.
6 Correct 149 ms 14364 KB Correct.
7 Correct 287 ms 19184 KB Correct.
8 Correct 201 ms 5964 KB Correct.
9 Correct 69 ms 3584 KB Correct.
10 Correct 64 ms 3544 KB Correct.
11 Correct 183 ms 4612 KB Correct.
12 Correct 77 ms 3532 KB Correct.
13 Correct 79 ms 3560 KB Correct.
14 Correct 306 ms 33760 KB Correct.
15 Correct 245 ms 11960 KB Correct.
16 Correct 77 ms 3660 KB Correct.
17 Correct 86 ms 3572 KB Correct.
18 Correct 79 ms 3556 KB Correct.
19 Correct 190 ms 4412 KB Correct.
20 Correct 8 ms 2772 KB Correct.
21 Correct 8 ms 3284 KB Correct.
22 Correct 15 ms 3796 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 3532 KB Correct.
2 Correct 25 ms 3876 KB Correct.
3 Incorrect 820 ms 72820 KB Wrong Answer.
4 Halted 0 ms 0 KB -