#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
template<typename T>
int len(T &a){
return a.size();
}
struct Segtree{
struct node{
int mx = 0;
void set(int x){
mx = max(mx, x);
}
node(int x){mx = x;}
node(){mx = 0;};
};
node merge(node a, node b){
return node(max(a.mx, b.mx));
}
vector<node> t;
int n;
void init(int _n){
n = _n;
t.resize(4 * n, node());
}
void upd(int x, int lx, int rx, int ind, int val){
if(lx == rx){
t[x].set(val); return;
}
int m = (lx + rx) / 2;
if(ind <= m){
upd(x * 2, lx, m, ind, val);
}else
upd(x * 2 + 1, m + 1, rx, ind, val);
t[x] = merge(t[x * 2], t[x * 2 + 1]);
}
node get(int x, int lx, int rx, int l, int r){
if(l <= lx && rx <= r) return t[x];
if(r < lx || rx < l){
return {0};
}
int m = (lx + rx) / 2;
return merge(get(x * 2, lx, m, l, r), get(x * 2 + 1, m + 1, rx, l, r));
}
void upd(int ind, int val){
upd(1, 0, n - 1, ind, val);
}
node get(int l, int r){
return get(1, 0, n - 1, l, r);
}
};
void sub3(int &n, int &m, int &k, vector<int> p,
vector<int> &v, vector<int> &day, vector<int> &cost){
//cout << "start" << endl;
for(int i = 1; i < n; i ++){
if(p[i] != i - 1) return;
}
for(int i = 0; i < m; i ++){
if(cost[i] != 1) return;
}
vector<int> fr(n);
for(int i = 0; i < m; i ++){
fr[v[i]] = day[i];
}
Segtree t; t.init(k + 1);
int ans = 0;
for(int i = n - 1; i > 0; i --){
if(fr[i] == 0) continue;
int mx = t.get(1, fr[i]).mx + 1;
ans = max(ans, mx);
t.upd(fr[i], mx);
}
cout << ans;// exit(0);
cout << endl;
}
void sub2(int &n, int &m, int &k, vector<int> p,
vector<int> &v, vector<int> &day, vector<int> &cost){
//cout << "start" << endl;
vector<vector<int>> g(n);
for(int i = 1; i < n; i ++){
g[p[i]].push_back(i);
}
ll ans = 0;
for(int i = 0; i < m; i ++){
if(len(g[v[i]])){return;}
ans += cost[i];
}
cout << ans; exit(0);
}
void sub5(int &n, int &m, int &k, vector<int> p,
vector<int> &v, vector<int> &day, vector<int> &cost){
//cout << "start" << endl;
vector<vector<int>> g(n);
for(int i = 1; i < n; i ++){
g[p[i]].push_back(i);
}
vector<int> fr(n), c(n);
for(int i = 0; i < m; i ++){
fr[v[i]] = day[i];
c[v[i]] = cost[i];
}
vector<vector<ll>> dp(n + 1, vector<ll> (k + 1, 0)),
pref(n + 1, vector<ll> (k + 1, 0));
auto dfs = [&](auto &dfs, int i)->void{
//cout << i + 1 << endl;
for(auto u : g[i]){
dfs(dfs, u);
}
for(int j = 1; j <= k; j ++){
ll s = (j == fr[i] ? c[i] : 0);
for(auto u : g[i]){
s += pref[u][j];
}
dp[i][j] = s;
pref[i][j] = max(pref[i][j - 1], dp[i][j]);
}
};
dfs(dfs, 0);
//cout << "d" << endl;
ll mx = 0;
for(int i = 0; i < n; i ++){
for(int j = 1; j <= k; j++){
mx = max(mx, dp[i][j]);
}
}
cout << mx << endl;;
exit(0);
}
void solve(){
int n, m, k; cin >> n >> m >> k;
vector<int> p(n), v(m), day(m), cost(m);
for(int i = 1; i < n; i ++){
cin >> p[i]; p[i] --;
}
for(int i = 0; i < m; i ++){
cin >> v[i] >> day[i] >> cost[i];
v[i] --;
}
sub2(n, m, k, p, v, day, cost);
sub3(n, m, k, p, v, day, cost);
sub5(n, m, k, p, v, day, cost);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int testcases = 1;
while(testcases --){
solve();
if(testcases) cout << '\n';
#ifdef LOCAL
else cout << '\n';
cout << "__________________________" << endl;
#endif
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
5144 KB |
Output is correct |
| 2 |
Correct |
16 ms |
6100 KB |
Output is correct |
| 3 |
Correct |
33 ms |
5136 KB |
Output is correct |
| 4 |
Correct |
29 ms |
5080 KB |
Output is correct |
| 5 |
Correct |
33 ms |
5364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
17840 KB |
Output is correct |
| 2 |
Correct |
71 ms |
19688 KB |
Output is correct |
| 3 |
Correct |
68 ms |
22280 KB |
Output is correct |
| 4 |
Correct |
42 ms |
18344 KB |
Output is correct |
| 5 |
Correct |
52 ms |
25492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
411 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
