oj.uz

Submission #771948

# Submission time Handle Problem Language Result Execution time Memory
771948 2023-07-03T12:33:47 Z Tenis0206 Cyberland (APIO23_cyberland) C++17
100 / 100
 1878 ms 124080 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int kmax = 120;
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 2732 KB Correct.
2 Correct 17 ms 2748 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3860 KB Correct.
2 Correct 24 ms 3868 KB Correct.
3 Correct 23 ms 3932 KB Correct.
4 Correct 25 ms 3880 KB Correct.
5 Correct 28 ms 3912 KB Correct.
6 Correct 25 ms 14164 KB Correct.
7 Correct 31 ms 14036 KB Correct.
8 Correct 22 ms 25664 KB Correct.
9 Correct 21 ms 2844 KB Correct.
10 Correct 21 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3920 KB Correct.
2 Correct 24 ms 3912 KB Correct.
3 Correct 23 ms 3940 KB Correct.
4 Correct 23 ms 2772 KB Correct.
5 Correct 30 ms 2772 KB Correct.
6 Correct 10 ms 12384 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 71772 KB Correct.
2 Correct 77 ms 3960 KB Correct.
3 Correct 68 ms 3968 KB Correct.
4 Correct 72 ms 3932 KB Correct.
5 Correct 48 ms 2840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3924 KB Correct.
2 Correct 22 ms 3972 KB Correct.
3 Correct 21 ms 3924 KB Correct.
4 Correct 26 ms 14368 KB Correct.
5 Correct 18 ms 2840 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3888 KB Correct.
2 Correct 20 ms 3924 KB Correct.
3 Correct 61 ms 91292 KB Correct.
4 Correct 19 ms 11128 KB Correct.
5 Correct 20 ms 2836 KB Correct.
6 Correct 21 ms 4012 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 4096 KB Correct.
2 Correct 15 ms 4692 KB Correct.
3 Correct 676 ms 114716 KB Correct.
4 Correct 280 ms 28116 KB Correct.
5 Correct 324 ms 49268 KB Correct.
6 Correct 162 ms 19292 KB Correct.
7 Correct 288 ms 30640 KB Correct.
8 Correct 204 ms 6772 KB Correct.
9 Correct 69 ms 4000 KB Correct.
10 Correct 65 ms 4044 KB Correct.
11 Correct 184 ms 4240 KB Correct.
12 Correct 83 ms 3944 KB Correct.
13 Correct 78 ms 3988 KB Correct.
14 Correct 319 ms 57528 KB Correct.
15 Correct 245 ms 17364 KB Correct.
16 Correct 73 ms 3964 KB Correct.
17 Correct 83 ms 3920 KB Correct.
18 Correct 80 ms 3932 KB Correct.
19 Correct 179 ms 3944 KB Correct.
20 Correct 6 ms 2772 KB Correct.
21 Correct 7 ms 3796 KB Correct.
22 Correct 14 ms 4180 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 3972 KB Correct.
2 Correct 46 ms 4812 KB Correct.
3 Correct 1493 ms 124080 KB Correct.
4 Correct 388 ms 12336 KB Correct.
5 Correct 1167 ms 51060 KB Correct.
6 Correct 529 ms 20200 KB Correct.
7 Correct 821 ms 46340 KB Correct.
8 Correct 340 ms 5836 KB Correct.
9 Correct 204 ms 4888 KB Correct.
10 Correct 191 ms 4940 KB Correct.
11 Correct 191 ms 3812 KB Correct.
12 Correct 234 ms 4892 KB Correct.
13 Correct 238 ms 4988 KB Correct.
14 Correct 1796 ms 50924 KB Correct.
15 Correct 1878 ms 61668 KB Correct.
16 Correct 497 ms 24432 KB Correct.
17 Correct 383 ms 7716 KB Correct.
18 Correct 222 ms 4524 KB Correct.
19 Correct 261 ms 4220 KB Correct.
20 Correct 231 ms 4300 KB Correct.
21 Correct 576 ms 3920 KB Correct.
22 Correct 11 ms 2800 KB Correct.
23 Correct 19 ms 3720 KB Correct.
24 Correct 40 ms 4180 KB Correct.