제출 #1157028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157028		SmuggingSpun	Magic Tree (CEOI19_magictree)	C++20	100 / 100	1053 ms	180036 KiB

magictree

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int n, m, k, vertex[lim], day[lim], weight[lim];
vector<int>g[lim];
namespace sub1{
	void solve(){
		vector<int>low(n + 1), tail(n + 1);
		int euler = -1;
		auto dfs = [&] (auto&& self, int s) -> void{
			low[s] = ++euler;
			for(int& d : g[s]){
				self(self, d);
			}	
			tail[s] = euler;
		};
		dfs(dfs, 1);
		vector<pair<int, int>>fruit(n, make_pair(-1, 0));
		for(int i = 1; i <= m; i++){
			fruit[low[vertex[i]]] = make_pair(day[i] - 1, weight[i]);
		}
		vector<vector<ll>>f(k, vector<ll>(1 << n, -1));
		auto dp = [&] (auto&& self, int p, int mask) -> ll{
			if(p == k){
				return 0;
			}	
			ll& ans = f[p][mask];
			if(ans != -1){
				return ans;
			}
			ans = self(self, p + 1, mask);
			for(int i = 2; i <= n; i++){
				if(1 << low[i] & mask){
					int nxt = mask;
					ll add = 0;
					for(int j = low[i]; j <= tail[i]; j++){
						if(1 << j & nxt){
							nxt ^= 1 << j;
							if(fruit[j].first == p){
								add += fruit[j].second;
							}
						}
					}
					maximize(ans, self(self, p, nxt) + add);
				}
			}
			return ans;
		};
		cout << dp(dp, 0, (1 << n) - 1);
	}
}
namespace sub2{
	void solve(){
		cout << accumulate(weight + 1, weight + m + 1, 0LL);
	}
}
namespace sub3{
	void solve(){
		vector<ll>bit(k + 1, 0);
		auto update = [&] (int p, ll x){
			for(; p <= k; p += p & -p){
				maximize(bit[p], x);
			}	
		};
		auto get = [&] (int p){
			ll ans = 0;
			for(; p > 0; p -= p & -p){
				maximize(ans, bit[p]);
			}	
			return ans;
		};
		vector<pair<int, int>>fruit(n + 1, make_pair(-1, 0));
		for(int i = 1; i <= m; i++){
			fruit[vertex[i]] = make_pair(day[i], weight[i]);
		}
		for(int i = n; i > 1; i--){
			if(fruit[i].first != -1){
				update(fruit[i].first, get(fruit[i].first) + fruit[i].second);
			}
		}
		cout << get(k);
	}
}
namespace sub45{
	void solve(){
		vector<vector<ll>>dp(n + 1, vector<ll>(k + 1, 0));
		vector<pair<int, int>>fruit(n + 1, make_pair(k, 0));
		for(int i = 1; i <= m; i++){
			fruit[vertex[i]] = make_pair(day[i], weight[i]);
		}
		auto dfs = [&] (auto&& self, int s) -> void{
			for(int& d : g[s]){
				self(self, d);
			}
			for(int i = 1; i <= k; i++){
				ll sum = 0;
				for(int& d : g[s]){
					sum += dp[d][i];
				}
				dp[s][i] = max(dp[s][i - 1], sum + (fruit[s].first == i ? fruit[s].second : 0));
			}
		};
		dfs(dfs, 1);
		cout << dp[1][k];
	}
}
namespace sub678{
	map<int, ll>cnt[lim];
	pair<int, int>benefit[lim];
	void dfs(int s){
		for(int& d : g[s]){
			dfs(d);
			if(cnt[d].size() > cnt[s].size()){
				swap(cnt[s], cnt[d]);
			}
			for(auto& [u, v] : cnt[d]){
				cnt[s][u] += v;
			}
		}
		int temp = benefit[s].second;
		cnt[s][benefit[s].first] += temp;
		vector<int>remove;
		for(auto it = cnt[s].upper_bound(benefit[s].first); it != cnt[s].end() && temp > 0; it = next(it)){
			if(it->second > temp){
				it->second -= temp;
				break;
			}
			else{
				remove.emplace_back(it->first);
				temp -= it->second;
			}
		}
		for(int& x : remove){
			cnt[s].erase(x);
		}
	}
	void solve(){
		fill(benefit + 1, benefit + n + 1, make_pair(k, 0));
		for(int i = 1; i <= m; i++){
			benefit[vertex[i]] = make_pair(day[i], weight[i]);
		}
		dfs(1);
		ll ans = 0;
		for(auto& [foo, v] : cnt[1]){
			ans += v;
		}
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> k;
	bool is_sub2 = true, is_sub3 = true;
	for(int i = 2; i <= n; i++){
		int x;
		cin >> x;
		if(x != i - 1){
			is_sub3 = false;
		}
		g[x].emplace_back(i);
	}
	for(int i = 1; i <= m; i++){
		cin >> vertex[i] >> day[i] >> weight[i];
		if(!g[vertex[i]].empty()){
			is_sub2 = false;
		}
	}
	if(max(n, k) <= 20){
		sub1::solve();
	}
	else if(is_sub2){
		sub2::solve();
	}
	else if(is_sub3){
		sub3::solve();
	}
	else if(k <= 20){
		sub45::solve();
	}
	else{
		sub678::solve();
	}
}

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

magictree.cpp: In function 'int main()':
magictree.cpp:160:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17