oj.uz

Submission #199745

# Submission time Handle Problem Language Result Execution time Memory
199745 2020-02-03T06:09:31 Z shahriarkhan Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 7 ms 2680 KB 
#include<bits/stdc++.h>
using namespace std ;

#define pii pair<int,int>

const int mx = 1e5 + 5 , inf = 1e9 + 10 ;

vector<pii> adj[mx] ;

int dist[mx] , vis[mx] , ans[mx][2] ;

int pass(int a , int d)
{
    if(d<=ans[a][0])
    {
        ans[a][1] = ans[a][0] ;
        ans[a][0] = d ;
        dist[a] = ans[a][1] ;
        return 1 ;
    }
    if(d<ans[a][1])
    {
        ans[a][1] = d ;
        dist[a] = d ;
        return 1 ;
    }
    return 0 ;
}

int travel_plan(int n , int m , int r[][2] , int l[] , int k , int p[])
{
    for(int i = 0 ; i < m ; ++i)
    {
        int a = r[i][0] , b = r[i][1] ;
        adj[a].push_back({b,l[i]}) ;
        adj[b].push_back({a,l[i]}) ;
    }

    for(int i = 0 ; i < n ; ++i) dist[i] = 0 , ans[i][0] = ans[i][1] = inf ;

    priority_queue<pii,vector<pii>,greater<pii> > pq ;

    for(int i = 0 ; i < k ; ++i)
    {
        pq.push({0,p[i]}) ;
        dist[p[i]] = 0 , ans[p[i]][0] = ans[p[i]][1] = 0 ;
    }

    while(!pq.empty())
    {
        pii pr = pq.top() ;
        pq.pop() ;
        int to = pr.second ;
        if(vis[to]) continue ;
        vis[to] = 1 ;
        int siz = adj[to].size() ;
        for(int i = 0 ; i < siz ; ++i)
        {
            int a = pr.first , b = pr.second ;
            int d = dist[to] + b ;
            if(pass(a,d)) pq.push({ans[a][1],a}) ;
        }
    }

    return ans[0][1] ;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -