제출 #1099673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099673		Saul0906	도로 폐쇄 (APIO21_roads)	C++14	0 / 100	163 ms	94600 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];
vector<pii> adj[lim];

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

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'void solve(int, int)':
roads.cpp:40:21: 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]
   40 |   while(pq[i].size()>i){
      |         ~~~~~~~~~~~~^~
roads.cpp:45:34: 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]
   45 |   if(pq[i].size() && pq[i].size()==i) dp[u][i][1]+=pq[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