oj.uz

Submission #771909

# Submission time Handle Problem Language Result Execution time Memory
771909 2023-07-03T11:44:03 Z Tenis0206 Cyberland (APIO23_cyberland) C++17
0 / 100
 3000 ms 25512 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int kmax = 30;
const int oo = INT_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];

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

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}});
    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)
            {
                new_t = 0;
            }
            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();
    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 1152 ms 3232 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1327 ms 7688 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 3036 ms 13664 KB Time limit exceeded
2 Halted 0 ms 0 KB -