Submission #1326150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326150		riafhasan2010	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	1 ms	568 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int travel_plan(int n, int m, int R[][2], int L[], int k, int p[]) {
  vector<pair<int, int>> g[n];
  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]});
  }
  vector<vector<ll>> cost(n);
  vector<int> vis(n, 0);
  queue<int> q;
  for (int i = 0; i < n; i++) {
    if (g[i].size() == 1) {
      vis[i] = 1;
      cost[i].resize(2, 0);
      q.push(i);
    }
  }
  while (!q.empty()) {
    auto u = q.front(); q.pop();
    sort(cost[u].begin(), cost[u].end());
    for (auto [v, w] : g[u]) {
      vis[v]++;
      cost[v].push_back(cost[u][1] + w);
      if(v and vis[v] == g[v].size() - 1) q.push(v);
    }
  }
  sort(cost[0].begin(), cost[0].end());
  return cost[0][1];
}

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