제출 #1117876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117876		vjudge1	Paprike (COI18_paprike)	C++17	0 / 100	754 ms	1048576 KiB

paprike

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

void dfs(const vector<vector<char>> &graph, vector<char> &visited, int node,
         int &sum, const vector<int> &values) {
  visited[node] = true;
  sum += values[node];
  for (size_t i = 0; i < graph.size(); i++) {
    if (graph[node][i] and !visited[i]) {
      dfs(graph, visited, i, sum, values);
    }
  }
}

int main() {
  bool bruteForce = true;
  int n, k, s = 0, ans = INT_MAX;
  cin >> n >> k;
  vector<int> h(n);
  vector<pair<int, int>> e(n - 1);
  for (int &s : h) {
    cin >> s;
  }
  for (auto &[a, b] : e) {
    cin >> a >> b;
    a--;
    b--;
    if (a + 1 != b) {
      bruteForce = false;
    }
  }

  if (bruteForce) {
    ans = 0;
    for (int i = 0; i < n; i++) {
      s += h[i];
      if (s > k) {
        ans++;
        s = h[i];
      }
    }
    cout << ans << '\n';
    return 0;
  }

  vector<vector<int>> allPermutations;
  vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};

  do {
    allPermutations.push_back(arr);
  } while (next_permutation(arr.begin(), arr.end()));

  for (int c = 0; c <= n - 1; c++) {
    for (const vector<int> &road : allPermutations) {
      unordered_set<int> cuts;
      vector<vector<char>> g(n, vector<char>(n, false));
      vector<char> v(n, false);
      for (int i = 0; i < c; i++) {
        cuts.insert(road[i]);
      }
      for (int i = 0; i < n - 1; i++) {
        if (cuts.find(i) != cuts.end()) {
          continue;
        }
        g[e[i].first][e[i].second] = true;
        g[e[i].second][e[i].first] = true;
      }
      int s = 0;
      for (int i = 0; i < n; i++) {
        if (!v[i]) {
          dfs(g, v, i, s, h);
          if (s >= k) {
            goto next;
          }
        }
      }
      ans = min(ans, c);
    next:
      continue;
    }
  }
  cout << ans << '\n';
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49