oj.uz

Submission #392891

# Submission time Handle Problem Language Result Execution time Memory
392891 2021-04-22T07:40:53 Z Hazem Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 2000 ms 5196 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Execution timed out 2084 ms 5196 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Execution timed out 2084 ms 5196 KB Time limit exceeded
10 Halted 0 ms 0 KB -