This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++){
if (!weight[i]) continue;
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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |