#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
int n,m,k;
vector<int> adj[100010];
int ripe[100010];
int weight[100010];
int memo[100010][1010];
int dp(int u,int j){
if (j == 0) return 0;
if (memo[u][j] != -1) return memo[u][j];
int s = 0;
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
s += dp(v,j);
}
if (j == ripe[u]) s += weight[u];
if (weight[u] != 0)return memo[u][j] = max(s,dp(u,j-1));
else return memo[u][j] = s;
}
struct node{
int s,e,m,v;
node *l,*r;
node (int _s,int _e){
s = _s;
e = _e;
m = (s+e)/2;
v = 0;
if (s != e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void up(int x,int v1){
if (s == e) {v = v1;return;}
if (x <= m) l->up(x,v1);
else r->up(x,v1);
v = max(l->v,r->v);
}
int rmq(int x,int y){
if (s == x && e == y) return v;
if (y <= m) return l->rmq(x,y);
if (x > m) return r->rmq(x,y);
return max(l->rmq(x,m),r->rmq(m+1,y));
}
}*root;
main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
int isline = 1;
for (int i = 2; i <= n; i++){
int p;
cin >> p;
if (i-1 != p) isline = 0;
adj[p].push_back(i);
}
vector<int> temp;
temp.push_back(0);
for (int i = 0; i < m; i++){
int v,d,w;
cin >> v >> d >> w;
ripe[v] = d;
weight[v] = w;
temp.push_back(d);
}
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(),temp.end()),temp.end());
for (int i = 1; i <= n; i++) ripe[i] = lower_bound(temp.begin(),temp.end(),ripe[i])-temp.begin();
//for (int i = 1; i <= n; i++) cout << ripe[i] << "\n";
if (k <= 20){
for (int i = 1; i<= n; i++){
for (int j = 0; j < temp.size(); j++){
memo[i][j] = -1;
}
}
cout << dp(1,temp.size()-1);
}
else if (isline){
int ans = 0;
root = new node(0,temp.size()-1);
for (int i = 1; i <= n; i++){
int q = root->rmq(0,ripe[i]);
ans = max(ans,q+weight[i]);
root->up(ripe[i],q+1);
}
cout << ans;
}
else{
int ans = 0;
for (int i = 1; i <= n; i++) ans += weight[i];
cout << ans;
}
}
Compilation message
magictree.cpp: In function 'long long int dp(long long int, long long int)':
magictree.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
magictree.cpp: At global scope:
magictree.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
magictree.cpp: In function 'int main()':
magictree.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < temp.size(); j++){
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
6 ms |
2816 KB |
Output is correct |
6 |
Correct |
6 ms |
2944 KB |
Output is correct |
7 |
Correct |
6 ms |
2816 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
6 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
6392 KB |
Output is correct |
2 |
Correct |
38 ms |
6524 KB |
Output is correct |
3 |
Correct |
74 ms |
6380 KB |
Output is correct |
4 |
Correct |
65 ms |
6648 KB |
Output is correct |
5 |
Correct |
71 ms |
6376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2816 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
258 ms |
410096 KB |
Output is correct |
2 |
Correct |
245 ms |
408560 KB |
Output is correct |
3 |
Correct |
231 ms |
412652 KB |
Output is correct |
4 |
Correct |
216 ms |
409072 KB |
Output is correct |
5 |
Correct |
230 ms |
416104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
6 ms |
2816 KB |
Output is correct |
6 |
Correct |
6 ms |
2944 KB |
Output is correct |
7 |
Correct |
6 ms |
2816 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
6 ms |
2816 KB |
Output is correct |
10 |
Correct |
289 ms |
424172 KB |
Output is correct |
11 |
Correct |
248 ms |
416364 KB |
Output is correct |
12 |
Correct |
255 ms |
426728 KB |
Output is correct |
13 |
Correct |
280 ms |
423164 KB |
Output is correct |
14 |
Correct |
266 ms |
430188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
3456 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
6 ms |
2816 KB |
Output is correct |
6 |
Correct |
6 ms |
2944 KB |
Output is correct |
7 |
Correct |
6 ms |
2816 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
6 ms |
2816 KB |
Output is correct |
10 |
Incorrect |
6 ms |
2816 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
6 ms |
2816 KB |
Output is correct |
6 |
Correct |
6 ms |
2944 KB |
Output is correct |
7 |
Correct |
6 ms |
2816 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
6 ms |
2816 KB |
Output is correct |
10 |
Correct |
49 ms |
6392 KB |
Output is correct |
11 |
Correct |
38 ms |
6524 KB |
Output is correct |
12 |
Correct |
74 ms |
6380 KB |
Output is correct |
13 |
Correct |
65 ms |
6648 KB |
Output is correct |
14 |
Correct |
71 ms |
6376 KB |
Output is correct |
15 |
Incorrect |
6 ms |
2816 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |