oj.uz

Submission #1096128

# Submission time Handle Problem Language Result Execution time Memory
1096128 2024-10-03T21:13:43 Z I_FloPPed21 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 3 ms 6236 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+1;
struct nod
{
    int unde;
    long long cost;
};

struct coada
{
    int unde;
    long long cost;
};

struct compare
{
    bool operator()(coada &x,coada &y)
    {
        return x.cost>y.cost;
    }
};
vector<nod>adj[N];
long long best[N][2];
bool found_first[N];
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    for(int i=0;i<m;i++)
    {
        adj[r[i][0]].push_back({r[i][1],l[i]});
        adj[r[i][1]].push_back({r[i][0],l[i]});
    }


    for(int i=0;i<n;i++)
    {
        best[i][0]=best[i][1]=1e12+1;
    }
    priority_queue<coada,vector<coada>,compare>pq;
    for(int i=0;i<k;i++)
    {
        best[p[i]][0]=0;
        best[p[i]][1]=0;
        pq.push({p[i],0});
    }
    while(!pq.empty())
    {
        int nod=pq.top().unde;
        long long cost=pq.top().cost;
        pq.pop();
        for(auto u:adj[nod])
        {
            if(best[u.unde][0]>cost+u.cost)
            {
                best[u.unde][1]=best[u.unde][0];
                best[u.unde][0]=cost+u.cost;
                if(found_first[u.unde])
                pq.push({u.unde,best[u.unde][1]});

                found_first[u.unde]=true;
            }
            else
                if(best[u.unde][1]>cost+u.cost)
            {
                best[u.unde][1]=cost+u.cost;
                pq.push({u.unde,best[u.unde][1]});
            }
        }
    }
    return best[0][1];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Incorrect 2 ms 6236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Incorrect 2 ms 6236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Incorrect 2 ms 6236 KB Output isn't correct
4 Halted 0 ms 0 KB -