Submission #1117668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117668		vjudge1	Paprike (COI18_paprike)	C++17	0 / 100	686 ms	1048576 KiB

paprike

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

void dfs(const vector<vector<int>> &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() {
  int n, k, x, y, s, ans;
  vector<int> h;
  vector<pair<int, int>> e;
  vector<vector<int>> g;
  vector<char> v;
  cin >> n >> k;
  g.resize(n, vector<int>(n, 0));
  h.resize(n);
  ans = n - 1;
  for (int &s : h) {
    cin >> s;
  }
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y;
    e.emplace_back(x - 1, y - 1);
  }
  sort(e.rbegin(), e.rend(),
       [&h](const pair<int, int> &p1, const pair<int, int> &p2) -> bool {
         return h[p1.first] + h[p1.second] < h[p2.first] + h[p2.second];
       });
  for (int i = 0; i < n - 1; i++) {
    x = e[i].first, y = e[i].second;
    v.assign(n, false);
    s = 0;
    g[x].push_back(y);
    g[y].push_back(x);
    for (int i = 0; i < n; i++) {
      if (!v[i]) {
        dfs(g, v, i, s, h);
        if (s >= k) {
          goto end;
        }
      }
    }
    ans = n - 1 - i;
  }

end:
  cout << ans << '\n';
  return 0;
}

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