Submission #392894

#	Time	Username	Problem	Language	Result	Execution time	Memory
392894		Hazem	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1074 ms	78756 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
 
#define S second
#define F first
#define LL long long 
 
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;

vector<pair<int,int>>adj[N1];
bool vis[N1];
LL mn1[N1],mn2[N1];

// LL dfs(int i){

//     if(vis[i])
//         return ans[i];

//     vis[i] = 1;
//     LL mn1 = LINF,mn2 = LINF;
//     for(auto x:adj[i]){
//         dfs(x.F);
//         if(ans[x.F]+x.S<mn1)mn2 = mn1,mn1 = ans[x.F]+x.S;
//         else if(ans[x.F]+x.S<mn2)mn2 = ans[x.F]+x.S;
//     }

//     ans1 = min(ans1,mn2);
//     return ans[i] = min(ans[i],mn2);
// }

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

    int n = N;
    
    for(int i=0;i<n;i++)
        mn1[i] = mn2[i] = LINF;

    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<K;i++)
        mn1[P[i]] = mn2[P[i]] = 0;
    
    priority_queue<pair<LL,int>>que;
    for(int i=0;i<n;i++)
        que.push({-mn2[i],i});

    while(!que.empty()){
        int u = que.top().S;
        LL ans = -que.top().F;
        que.pop();

        if(vis[u])continue;
        vis[u] = 1;

        //printf("%d %lld\n",u,ans);
        
        for(auto x:adj[u]){
            int v = x.F;
            //printf("%d %d %d\n",u,v,x.S);

            if(ans+x.S<mn1[v])
                mn2[v] = mn1[v],mn1[v] = ans+x.S;
            else 
                if(ans+x.S<mn2[v])
                    mn2[v] = ans+x.S;
            que.push({-mn2[v],v});
        }
    }
    return mn2[0];
}


/*
#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

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