oj.uz

Submission #771942

# Submission time Handle Problem Language Result Execution time Memory
771942 2023-07-03T12:30:35 Z Tenis0206 Cyberland (APIO23_cyberland) C++17
97 / 100
 599 ms 47312 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int kmax = 30;
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 2772 KB Correct.
2 Correct 17 ms 2848 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3092 KB Correct.
2 Correct 33 ms 3132 KB Correct.
3 Correct 23 ms 3136 KB Correct.
4 Correct 23 ms 3128 KB Correct.
5 Correct 23 ms 3136 KB Correct.
6 Correct 28 ms 6512 KB Correct.
7 Correct 35 ms 6372 KB Correct.
8 Correct 14 ms 10284 KB Correct.
9 Correct 21 ms 2644 KB Correct.
10 Correct 23 ms 2768 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3112 KB Correct.
2 Correct 29 ms 3160 KB Correct.
3 Correct 23 ms 3156 KB Correct.
4 Correct 24 ms 2780 KB Correct.
5 Correct 33 ms 2760 KB Correct.
6 Correct 9 ms 5992 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 25684 KB Correct.
2 Correct 81 ms 3168 KB Correct.
3 Correct 72 ms 4032 KB Correct.
4 Correct 72 ms 4064 KB Correct.
5 Correct 49 ms 3532 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3176 KB Correct.
2 Correct 21 ms 3164 KB Correct.
3 Correct 21 ms 3232 KB Correct.
4 Correct 24 ms 6676 KB Correct.
5 Correct 21 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3156 KB Correct.
2 Correct 21 ms 3124 KB Correct.
3 Correct 55 ms 31368 KB Correct.
4 Correct 16 ms 5716 KB Correct.
5 Correct 27 ms 2760 KB Correct.
6 Correct 20 ms 3168 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3208 KB Correct.
2 Correct 17 ms 3556 KB Correct.
3 Correct 599 ms 41616 KB Correct.
4 Correct 265 ms 13280 KB Correct.
5 Correct 284 ms 22768 KB Correct.
6 Correct 151 ms 12516 KB Correct.
7 Correct 275 ms 13736 KB Correct.
8 Correct 203 ms 5908 KB Correct.
9 Correct 80 ms 4120 KB Correct.
10 Correct 77 ms 4056 KB Correct.
11 Correct 189 ms 5144 KB Correct.
12 Correct 79 ms 3880 KB Correct.
13 Correct 78 ms 4036 KB Correct.
14 Correct 275 ms 22424 KB Correct.
15 Correct 246 ms 9576 KB Correct.
16 Correct 85 ms 4064 KB Correct.
17 Correct 84 ms 4164 KB Correct.
18 Correct 77 ms 4164 KB Correct.
19 Correct 190 ms 5028 KB Correct.
20 Correct 6 ms 2772 KB Correct.
21 Correct 8 ms 3068 KB Correct.
22 Correct 14 ms 3668 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3212 KB Correct.
2 Correct 19 ms 3556 KB Correct.
3 Incorrect 393 ms 47312 KB Wrong Answer.
4 Halted 0 ms 0 KB -