oj.uz

Submission #564674

# Submission time Handle Problem Language Result Execution time Memory
564674 2022-05-19T12:54:17 Z Karliver Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 44236 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)


long long dp[N][21];
bool on[N];
int n, m, k;
int D[N], V[N], W[N];
vector<int> g[N];
long long  dfs(int v, int lm) {
	if(dp[v][lm] != -1)
		return dp[v][lm];
	
	long long &ret = dp[v][lm];
	ret = 0;
	for(auto c : g[v]) {
		long long ps = 0;
		if(on[c] && lm >= D[c])
			ps = max(ps, dfs(c, D[c]) + W[c]);
		ps = max(ps, dfs(c, lm));
		ret += ps;
		
	}
	
	return ret;
}
void test_case() {
	
	
	
	cin >> n >> m >> k;
	
	
	
	
	for(int  j = 1;j < n;++j) {
		int x;
		cin >> x;
		--x;
		g[x].push_back(j);
	}
	
	for(int i = 0;i < m;++i) {
		int v, d, w;
		cin >> v >> d >> w;
		--v;
		on[v] = 1;
		D[v] = d;
		W[v] = w;
	}
	for(int j = 0;j < n;++j) for(int l = 0;l <= k;++l) dp[j][l] = -1;
	
	cout << dfs(0, k) << '\n';
	
	
	
}
					
		

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;
	tt = 1;
	//cin >> tt;
	
	for(int p = 1;p <= tt;++p) {
		//cout << "Case #" << p << ": ";
		test_case();
	}
	
		
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 44236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2900 KB Output is correct
2 Incorrect 3 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23700 KB Output is correct
2 Correct 99 ms 23692 KB Output is correct
3 Correct 69 ms 28376 KB Output is correct
4 Correct 54 ms 22264 KB Output is correct
5 Correct 77 ms 34584 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 133 ms 23076 KB Output is correct
11 Correct 85 ms 23028 KB Output is correct
12 Correct 215 ms 27736 KB Output is correct
13 Correct 39 ms 21632 KB Output is correct
14 Correct 121 ms 34000 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 6988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 3 ms 2900 KB Output is correct
11 Incorrect 3 ms 2900 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Execution timed out 2062 ms 44236 KB Time limit exceeded
11 Halted 0 ms 0 KB -