제출 #1298276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298276		herominhsteve	Paprike (COI18_paprike)	C++20	100 / 100	34 ms	21272 KiB

paprike

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 100'005;

int n,K;
vector<int> val;
vector<int> graph[MAXN];

void init(){
	cin>>n>>K;
	val.resize(n);
	for (int &x : val) cin>>x;
	for (int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
}

vector<int> dp;
vector<int> sumW;

void dfs(int u=0,int pre=-1){
	sumW[u] = val[u];
	vector<pair<int,int>> child; child.reserve(graph[u].size());
	for (int v : graph[u]) if (v ^ pre){
		dfs(v,u);
		child.emplace_back(sumW[v],v);
	}
	sort(allof(child));
	for (const pair<int,int> &p : child){
		int w,v; tie(w,v) = p;
		dp[u] += dp[v];
		if (sumW[u] <= K - w) sumW[u] += w;
		else dp[u]++;
	}
}

void sol(){
	dp.assign(n,0);
	sumW.assign(n,0);
	dfs();
	cout<<dp.front();
}

int main(){
    setup();
    init();
    sol();
}

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

paprike.cpp: In function 'void setup()':
paprike.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paprike.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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