Submission #494932

#	Time	Username	Problem	Language	Result	Execution time	Memory
494932		YJU	Magic Tree (CEOI19_magictree)	C++17	100 / 100	124 ms	40796 KiB

magictree

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll INF = (1LL<<60);
const ll N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ld pi = acos(-1);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
#define setp setprecision

typedef map<ll, ll> mll;

ll d[N], w[N], n, m, t;
vector<ll> v[N];
mll *dp[N];

void insert(mll *a, pll k) {
	ll last = k.se;
	for (auto i = (*a).lwb(k.fi+1);i != (*a).end(); i = (*a).lwb(i->fi+1)) {
		if (i->se > last) {
			i->se -= last;
			break;
		} else {
			last -= i->se;
			(*a).erase(i);
		}
	}
	(*a)[k.fi] += k.se;
}

mll* mg(mll *a, mll *b) {
	if (SZ((*a)) > SZ((*b))) swap(a, b);
	for (auto i : (*a)) (*b)[i.fi] += i.se;
	return b;
}

void DFS(ll now) {
	dp[now] = new mll;
	for (ll to : v[now]) {
		DFS(to);
		dp[now] = mg(dp[now], dp[to]);
	}
	if (w[now]) {
		insert(dp[now], {d[now], w[now]});
	}
}


int main () {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> t;
	for (ll i = 2, x;i <= n; ++i) {
		cin >> x;
		v[x].pb(i);
	}
	for (ll i = 0, x;i < m; ++i) {
		cin >> x;
		cin >> d[x] >> w[x];
	}
	DFS(1);
	ll ans = 0;
	for (auto i : (*dp[1])) {
		ans += i.se;
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

magictree.cpp:2:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
      |                                                               ^
magictree.cpp:2:63: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
magictree.cpp:25:26: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   25 | void insert(mll *a, pll k) {
      |                          ^
magictree.cpp:25:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:39:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   39 | mll* mg(mll *a, mll *b) {
      |                       ^
magictree.cpp:39:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:45:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   45 | void DFS(ll now) {
      |                ^
magictree.cpp:45:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:57:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   57 | int main () {
      |           ^
magictree.cpp:57:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

• 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