Submission #200819

#	Time	Username	Problem	Language	Result	Execution time	Memory
200819		shahriarkhan	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	740 ms	63960 KiB

crocodile

#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 push_down(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] = dist[a] = d ;
        return 1 ;
    }
    return 0 ;
}

void djikstra(int n , int m , int r[][2] , int l[] , int k , int p[])
{
    for(int i = 0 ; i < n ; ++i) dist[i] = 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]] = 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)
        {
            pr = adj[to][i] ;
            int a = pr.first , b = pr.second ;
            int d = dist[to] + b ;
            if(push_down(a,d)) pq.push({ans[a][1],a}) ;
        }
    }
}

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]}) ;
    }
    djikstra(n,m,r,l,k,p) ;
    return ans[0][1] ;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11