Submission #896432

#	Time	Username	Problem	Language	Result	Execution time	Memory
896432		anton	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	165 ms	262144 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>

vector<vector<pii>> adj;

vector<bool> is_exit;

const int INF = 1e9 +2;

int dfs(int u, int a){
  if(is_exit[u]){
    return 0;
  }
  else{
    int MIN = INF;
    int sMIN = INF;
    for(auto e: adj[u]){
      if(e.first!=a){
        int res = dfs(e.first, u)+ e.second;
        if(res<=MIN){
          sMIN = MIN;
          MIN= res;
        }
        else if(res<=sMIN){
          sMIN = res;
        }
      }
    }
    return sMIN;
  }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  adj.resize(N);
  is_exit.resize(N);

  for(int i = 0; i<K; i++){
    is_exit[P[i]] = true;
  }
  for(int i = 0; i<M; i++){
    adj[R[i][0]].push_back(pii(R[i][1], L[i]));
    adj[R[i][1]].push_back(pii(R[i][0], L[i]));
  }

  return dfs(0, -1);
}

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