oj.uz

Submission #531697

# Submission time Handle Problem Language Result Execution time Memory
531697 2022-03-01T09:57:03 Z Yazan_Alattar Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 797812 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector <int> adj[M];
int n, m, k, ripe[M], w[M], vert[M];
ll dp[M][1007];

void dfs(int node){
	for(auto i : adj[node]){
		dfs(i);
		for(int j = 1; j <= k; ++j) dp[node][j] += dp[i][j];	
	}
	dp[node][ripe[node]] += w[node];
	
	for(int i = 1; i <= k; ++i) dp[node][i] = max(dp[node][i], dp[node][i - 1]);
	return;
}

int main(){
	scanf("%d%d%d", &n, &m, &k); k = min(k, m);
	for(int i = 2; i <= n; ++i){
		int p; scanf("%d", &p);
		adj[p].pb(i);
	}
	
	vector <int> v;
	for(int i = 1; i <= m; ++i){
		scanf("%d", &vert[i]);
		scanf("%d%d", &ripe[vert[i]], &w[vert[i]]);
		v.pb(ripe[vert[i]]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for(int i = 1; i <= m; ++i)
		for(int j = 0; j < (int)v.size(); ++j)
			if(v[j] == ripe[vert[i]]){ripe[vert[i]] = j + 1; break;}
		
	dfs(1);
	printf("%lld\n", dp[1][k]);
	return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d%d", &n, &m, &k); k = min(k, m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:35:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   int p; scanf("%d", &p);
      |          ~~~~~^~~~~~~~~~
magictree.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d", &vert[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
magictree.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d", &ripe[vert[i]], &w[vert[i]]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10572 KB Output is correct
2 Correct 8 ms 10592 KB Output is correct
3 Correct 7 ms 10572 KB Output is correct
4 Execution timed out 2069 ms 33048 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 410328 KB Output is correct
2 Correct 223 ms 409548 KB Output is correct
3 Correct 231 ms 414488 KB Output is correct
4 Correct 193 ms 408732 KB Output is correct
5 Correct 225 ms 419716 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 248 ms 423804 KB Output is correct
11 Correct 273 ms 415804 KB Output is correct
12 Correct 229 ms 427788 KB Output is correct
13 Correct 206 ms 422124 KB Output is correct
14 Correct 212 ms 433088 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 160892 KB Output is correct
2 Correct 700 ms 793836 KB Output is correct
3 Correct 733 ms 793856 KB Output is correct
4 Correct 832 ms 793780 KB Output is correct
5 Correct 849 ms 792460 KB Output is correct
6 Correct 809 ms 795188 KB Output is correct
7 Correct 752 ms 797812 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 8 ms 10572 KB Output is correct
11 Correct 8 ms 10592 KB Output is correct
12 Correct 7 ms 10572 KB Output is correct
13 Execution timed out 2069 ms 33048 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Execution timed out 2093 ms 782796 KB Time limit exceeded
11 Halted 0 ms 0 KB -