oj.uz

Submission #494930

# Submission time Handle Problem Language Result Execution time Memory
494930 2021-12-17T15:04:20 Z YJU Magic Tree (CEOI19_magictree) C++14
34 / 100
 812 ms 1048580 KB 
#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 = 1e6 + 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;
// FOR DEBUG PURPOSE

ostream& operator << (ostream& out, mll k) {
	for (auto i : k) {
		out << "{" << i.fi << ", " << i.se << "} ";
	}
	return out;
}

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) {
	for (ll to : v[now]) {
		DFS(to);
		dp[now] = mg(dp[now], dp[to]);
	}
	if (w[now]) {
		insert(dp[now], {d[now], w[now]});
	}
	//cout << "NODE::" << now << " " << dp[now] << "\n";
	/*
	for (ll j = 0;j <= t; ++j) {
		dp[now][j] = (j == d[now] ? w[now] : 0);
		for (ll to : v[now]) {
			ll ma = 0;
			for (ll k = 0;k <= j; ++k) {
				ma = max(ma, dp[to][k]);
			}
			dp[now][j] += ma;
		}
	}
	*/
}


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

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:22:42: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   22 | ostream& operator << (ostream& out, mll k) {
      |                                          ^
magictree.cpp:22:42: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:33:26: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   33 | void insert(mll &a, pll k) {
      |                          ^
magictree.cpp:33:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:47:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   47 | mll& mg(mll &a, mll &b) {
      |                       ^
magictree.cpp:47:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:53:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   53 | void DFS(ll now) {
      |                ^
magictree.cpp:53:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:77:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   77 | int main () {
      |           ^
magictree.cpp:77:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 36 ms 70688 KB Output is correct
3 Correct 32 ms 70708 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 32 ms 70724 KB Output is correct
6 Correct 33 ms 70776 KB Output is correct
7 Correct 34 ms 70732 KB Output is correct
8 Correct 33 ms 70764 KB Output is correct
9 Correct 35 ms 70776 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 222024 KB Output is correct
2 Runtime error 812 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 71080 KB Output is correct
2 Correct 38 ms 72436 KB Output is correct
3 Correct 45 ms 83268 KB Output is correct
4 Correct 112 ms 122392 KB Output is correct
5 Runtime error 736 ms 1048580 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 84108 KB Output is correct
2 Correct 105 ms 82304 KB Output is correct
3 Correct 95 ms 93868 KB Output is correct
4 Correct 81 ms 87408 KB Output is correct
5 Correct 90 ms 100968 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 36 ms 70688 KB Output is correct
3 Correct 32 ms 70708 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 32 ms 70724 KB Output is correct
6 Correct 33 ms 70776 KB Output is correct
7 Correct 34 ms 70732 KB Output is correct
8 Correct 33 ms 70764 KB Output is correct
9 Correct 35 ms 70776 KB Output is correct
10 Correct 159 ms 107204 KB Output is correct
11 Correct 140 ms 98504 KB Output is correct
12 Correct 217 ms 202836 KB Output is correct
13 Correct 212 ms 199364 KB Output is correct
14 Correct 190 ms 205708 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 73672 KB Output is correct
2 Correct 70 ms 78512 KB Output is correct
3 Correct 77 ms 78152 KB Output is correct
4 Correct 68 ms 79676 KB Output is correct
5 Runtime error 773 ms 1048580 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 36 ms 70688 KB Output is correct
3 Correct 32 ms 70708 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 32 ms 70724 KB Output is correct
6 Correct 33 ms 70776 KB Output is correct
7 Correct 34 ms 70732 KB Output is correct
8 Correct 33 ms 70764 KB Output is correct
9 Correct 35 ms 70776 KB Output is correct
10 Correct 35 ms 71080 KB Output is correct
11 Correct 38 ms 72436 KB Output is correct
12 Correct 45 ms 83268 KB Output is correct
13 Correct 112 ms 122392 KB Output is correct
14 Runtime error 736 ms 1048580 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 36 ms 70688 KB Output is correct
3 Correct 32 ms 70708 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 32 ms 70724 KB Output is correct
6 Correct 33 ms 70776 KB Output is correct
7 Correct 34 ms 70732 KB Output is correct
8 Correct 33 ms 70764 KB Output is correct
9 Correct 35 ms 70776 KB Output is correct
10 Correct 264 ms 222024 KB Output is correct
11 Runtime error 812 ms 1048580 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -