Submission #1099667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099667		Saul0906	Road Closures (APIO21_roads)	C++14	0 / 100	224 ms	219732 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define rep2(a,b,c,d) for(int a=b; a<c; a+=d)
#define repa(a,b) for(auto a:b)
#define fi first
#define se second
#define pb push_back
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>

using namespace std;

using ll = long long int;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int lim=2005;
const ll inf=1e18;
ll dp[lim][lim][2], n;
pq_min(ll) pq[lim][lim];
vector<pii> adj[lim];

void solve(int u, int p){
	dp[u][0][1]=inf;
	repa(v,adj[u]){
		if(v.fi==p) continue;
		solve(v.fi,u);
		repr(i,n,0){
			pq[u][i].push(dp[v.fi][i][0]+v.se-dp[v.fi][i][1]);
			dp[u][i][0]+=dp[v.fi][i][1];
			dp[u][i][1]+=dp[v.fi][i][1];
		}
	}
	rep(i,0,n){
		while(pq[u][i].size()>i){
			dp[u][i][0]+=pq[u][i].top();
			dp[u][i][1]+=pq[u][i].top();
			pq[u][i].pop();
		}
		if(pq[u][i].size() && pq[u][i].size()==i) dp[u][i][1]+=pq[u][i].top();
		if(!i) dp[u][i][1]=inf;
		while(pq[u][i].size()) pq[u][i].pop();
	}
}

vll minimum_closure_costs(int N, vi U, vi V, vi W) {
	if(N>=lim) return vll(N, 0);
	n=N;
	rep(i,0,n-1) adj[U[i]].pb({V[i],W[i]}), adj[V[i]].pb({U[i],W[i]});
	solve(0,-1);
	vll ans;
	rep(i,0,n) ans.pb(min(dp[0][i][0],dp[0][i][1]));
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void solve(int, int)':
roads.cpp:38:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   while(pq[u][i].size()>i){
      |         ~~~~~~~~~~~~~~~^~
roads.cpp:43:40: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   if(pq[u][i].size() && pq[u][i].size()==i) dp[u][i][1]+=pq[u][i].top();
      |                         ~~~~~~~~~~~~~~~^~~

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