Submission #392891

#	Time	Username	Problem	Language	Result	Execution time	Memory
392891		Hazem	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	2084 ms	5196 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 ans[N1],ans1 = LINF;

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;
    }

    vis[i] = 0;
    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++)
        ans[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++)
        vis[P[i]] = 1,ans[P[i]] = 0;

    dfs(0);
    return ans[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: 0 / 43
• Subtask 3: 0 / 11