Submission #414057

#	Time	Username	Problem	Language	Result	Execution time	Memory
414057		flashmt	Road Closures (APIO21_roads)	C++17	12 / 100	78 ms	11860 KiB

roads

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;

int n;
vector<pair<int, int>> a[100100];

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  n = N;
  int isLine = 1;
  for (int i = 0; i < n - 1; i++)
  {
    a[U[i]].push_back({V[i], W[i]});
    a[V[i]].push_back({U[i], W[i]});
    if (U[i] != i || V[i] != i + 1)
      isLine = 0;
  }
  vector<long long> ans(n);
  ans[0] = accumulate(W.begin(), W.end(), 0LL);
  // cout << ans[0] << endl;

  // 1
  if (a[0].size() == n - 1)
  {
    sort(W.begin(), W.end(), greater<int>());
    for (int i = n - 2; i >= 0; i--)
      ans[i] = ans[i + 1] + W[i];
    return ans;
  }

  // 2
  if (isLine)
  {
    vector<long long> f(n, oo);
    f[0] = 0;
    f[1] = W[0];
    for (int i = 2; i < n; i++)
      f[i] = min(f[i - 1], f[i - 2]) + W[i - 1];
    ans[1] = min(f[n - 1], f[n - 2]);
  }

  return ans;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:23:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |   if (a[0].size() == n - 1)
      |       ~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22