oj.uz

Submission #771922

# Submission time Handle Problem Language Result Execution time Memory
771922 2023-07-03T12:09:31 Z Tenis0206 Cyberland (APIO23_cyberland) C++17
37 / 100
 3000 ms 32784 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<int,pair<int,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<=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,{it,0}});
    }
    while(!h.empty())
    {
        while(!h.empty() && sel[h.top().second.first][h.top().second.second])
        {
            h.pop();
        }
        if(h.empty())
        {
            return;
        }
        int nod = h.top().second.first;
        int nr = h.top().second.second;
        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({d[it.first][nr],{it.first,nr}});
            }
            if(tip[it.first]==2 && nr < k)
            {
                if(new_t * 0.5 < d[it.first][nr + 1])
                {
                    d[it.first][nr+1] = new_t * 0.5;
                    h.push({d[it.first][nr+1],{it.first,nr+1}});
                }
            }
        }
        if(tip[nod]==2 && nr < k)
        {
            double new_t = (d[nod][nr] + 2) * 0.5;
            if(new_t < d[nod][nr + 1])
            {
                d[nod][nr + 1] = new_t;
                h.push({d[nod][nr+1],{nod,nr+1}});
            }
        }
    }
}

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<=k;p++)
    {
        rez = min(rez, d[f][p]);
    }
    return rez;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2772 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3116 KB Correct.
2 Correct 24 ms 4064 KB Correct.
3 Correct 23 ms 4064 KB Correct.
4 Correct 23 ms 4004 KB Correct.
5 Correct 25 ms 4064 KB Correct.
6 Correct 21 ms 7252 KB Correct.
7 Correct 27 ms 7216 KB Correct.
8 Correct 15 ms 10484 KB Correct.
9 Correct 25 ms 3496 KB Correct.
10 Correct 21 ms 3444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3116 KB Correct.
2 Correct 26 ms 3860 KB Correct.
3 Correct 22 ms 3932 KB Correct.
4 Correct 25 ms 3236 KB Correct.
5 Correct 23 ms 3532 KB Correct.
6 Correct 7 ms 5964 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 26088 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3084 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3192 KB Correct.
2 Correct 19 ms 3964 KB Correct.
3 Correct 44 ms 32784 KB Correct.
4 Correct 16 ms 6228 KB Correct.
5 Correct 20 ms 3540 KB Correct.
6 Correct 24 ms 3824 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 3340 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 24188 KB Time limit exceeded
2 Halted 0 ms 0 KB -