Submission #821740

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

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
     
using namespace std;
using ll = long long int;
     
vector<pair<int,ll>> g[100100];
     
ll dist[100100] = {0};
bool exit_c[100100] = {false};

void dfs(int node, int prev = -1){
      for(auto i : g[node]){
        if(i.first != prev){
          dist[i.first] = dist[node] + i.second;
          dfs(i.first, node);
        }
      }
}

int solve(int node, int prev = -1){
  if(exit_c[node]) return 0;
  vector<int> v;
  for(auto i : g[node]){
    if(i.first != prev){
      int s = solve(i.first,node) + i.second;
      v.push_back(s);
    }
  }
  sort(begin(v), end(v));
  return v[1];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i = 0; i < M; ++i){
    g[R[i][0]].push_back({R[i][1], L[i]});
    g[R[i][1]].push_back({R[i][0], L[i]});
  }
  for(int i = 0; i < K; ++i){
    exit_c[P[i]] = true;
  }
  dfs(0);
  return solve(0);
}

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