Submission #981356

#	Time	Username	Problem	Language	Result	Execution time	Memory
981356		Jawad_Akbar_JJ	Road Closures (APIO21_roads)	C++17	12 / 100	43 ms	6640 KiB

roads

#include <iostream>
#include <vector>
#include <algorithm>
#include "roads.h"

using namespace std;
#define ll long long
const int N = 1e5 + 10;
vector<pair<int,int>> nei[N];

vector<ll> sub1(int n,vector<int> W){
	sort(rbegin(W),rend(W));
	vector<ll> v;
	v.push_back(0);
	for (int i : W)
		v[0] += i;
	for (int i : W)
		v.push_back(v.back() - i);
	return v;
}

vector<ll> sub2(int n,vector<int> W){
	ll t = W[0];
	ll nt = 0;
	vector<ll> v(n,0);
	v[0] += W[0];
	for (int i=1;i<n-1;i++){
		ll a = t;
		t = min(t,nt) + W[i];
		nt = a;
		v[0] += W[i];
	}
	v[1] = min(t,nt);
	return v;
}

vector<ll>  minimum_closure_costs(int n,vector<int> U,vector<int> V,vector<int> W){
	long long sum = 0,sum2 = 0,sum3 = 0;

	for (int i=0;i<n-1;i++)
		sum += U[i],sum2 += W[i],sum3 += (U[i] == i);
	
	if (sum == 0)
		return sub1(n,W);
	
	// if (sum2 == n-1)
	// 	return sub5(n,U,V);
	if (sum3 == n-1)
		return sub2(n,W);
}

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:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

• 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