oj.uz

Submission #855632

# Submission time Handle Problem Language Result Execution time Memory
855632 2023-10-01T14:42:16 Z mychecksedad Magic Tree (CEOI19_magictree) C++17
33 / 100
 780 ms 680168 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e5+100, M = 1e5, K = 1e3+10;
 
 
int ttt = 1;
struct Node{
  Node *L, *R;
  ll val, lazy, lazy2, settime, addtime;
  Node(){
    L = R = nullptr;
    val = 0;
    lazy = lazy2 = 0;
    settime = 0;
    addtime = 0;
  }
  void extend(){
    if(L == nullptr) L = new Node();
    if(R == nullptr) R = new Node();
  }
  void push(){
    if(addtime == 0){
      if(settime > 0){
        if(lazy2 >= L->val){
          L->val = max(lazy2, L->val);
          L->lazy2 = max(lazy2, L->lazy2);
          L->settime = settime;
          L->lazy = L->addtime = 0;
        }
        if(lazy2 >= R->val){
          R->val = max(lazy2, R->val);
          R->lazy2 = max(lazy2, R->lazy2);
          R->settime = settime;
          R->lazy = R->addtime = 0;
        }
        lazy2 = settime = 0;
      }
    }else{
      if(settime == 0){
        L->val += lazy;
        R->val += lazy;
        L->lazy += lazy;
        R->lazy += lazy;
        L->addtime = addtime; 
        R->addtime = addtime;
        lazy = addtime = 0;
      }else{
        if(settime < addtime){
          if(lazy2 >= L->val){
            L->val = max(lazy2, L->val);
            L->lazy2 = max(lazy2, L->lazy2);
            L->settime = settime;
            L->lazy = L->addtime = 0;
          }
          if(lazy2 >= R->val){
            R->val = max(lazy2, R->val);
            R->lazy2 = max(lazy2, R->lazy2);
            R->settime = settime;
            R->lazy = R->addtime = 0;
          }
          lazy2 = settime = 0;
 
          L->val += lazy;
          R->val += lazy;
          L->lazy += lazy;
          R->lazy += lazy;
          L->addtime = addtime;
          R->addtime = addtime;
          lazy = addtime = 0;
        }else{
          L->val += lazy;
          R->val += lazy;
          L->lazy += lazy;
          R->lazy += lazy;
          L->addtime = addtime;
          R->addtime = addtime;
          lazy = addtime = 0;
 
          if(lazy2 >= L->val){
            L->val = max(lazy2, L->val);
            L->lazy2 = max(lazy2, L->lazy2);
            L->lazy = L->addtime = 0;
            L->settime = settime;
          }
          if(lazy2 >= R->val){
            R->val = max(lazy2, R->val);
            R->lazy2 = max(lazy2, R->lazy2);
            R->lazy = R->addtime = 0;
            R->settime = settime;
          }
          lazy2 = settime = 0;
        }
      }
    }
  }
 
  void range_update(int l, int r, int ql, int qr, ll x){
    if(ql > r || l > qr) return;
    if(ql <= l && r <= qr){
      extend();
      push();
      val += x;
      lazy += x;
      addtime = ttt++;
      return;
    }
    extend();
    push();
    int m = l+r>>1;
    L->range_update(l, m, ql, qr, x);
    R->range_update(m+1, r, ql, qr, x);
    val = max(L->val, R->val);
  }
  void range_update_max(int l, int r, int ql, int qr, ll x){
    if(ql > r || l > qr) return;
    if(ql <= l && r <= qr){
      extend();
      push();
      val = max(x, val);
      lazy2 = max(lazy2, x);
      settime = ttt++;
      return;
    }
    extend();
    push();
    int m = l+r>>1;
    L->range_update_max(l, m, ql, qr, x);
    R->range_update_max(m+1, r, ql, qr, x);
    val = max(L->val, R->val);
  }
  ll get(int l, int r, int p){
    if(r <= p) return val;
    extend();
    push();
    int m = l+r>>1;
    if(p <= m)
      return L->get(l, m, p);
    return max(L->val, R->get(m+1, r, p));
  }
};
 
int n, m, k, sz[N], d[N];
vector<int> g[N], T_time[N];
ll w[N];
vector<Node*> T;
 
void pre(int v){
  sz[v] = 1;
  for(int &u: g[v]){
    pre(u);
    sz[v] += sz[u];
    if(sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
  }
}
 
void dfs(int v){
  int big = g[v].empty() ? -1 : g[v][0];
  for(int u: g[v]){
    dfs(u);
    if(d[u] > 0){
      ll val = T[u]->get(1, M, d[u]) + w[u];
      T[u]->range_update_max(1, M, d[u], M, val);
      T_time[u].pb(d[u]);
      // cout << d[u] << ' ' << w[u] << ' ' << u << '\n';
    }
  }
  
  if(big != -1){
    swap(T[v], T[big]);
    T_time[v].swap(T_time[big]);
  }else{
    T[v] = new Node();
  }
 
  for(int u: g[v]){
    if(u == big) continue;
    sort(all(T_time[u]), greater<int>());
    int last = M;
    for(int tm: T_time[u]){
      if(tm > last) continue;
      // cout << v << ' ' << u << ' ' << tm << '\n';
      ll val = T[u]->get(1, M, tm);
      // cout << val << '\n';
      T[v]->range_update(1, M, tm, last, val);
      
      T_time[v].pb(tm);
 
      last = tm - 1;
    }
  }
 
}
 
 
void solve(){
  cin >> n >> m >> k;
  for(int i = 2; i <= n; ++i){
    int p; cin >> p;
    g[p].pb(i);
  }
  for(int i = 0; i <= n; ++i) d[i] = w[i] = 0;
  vector<int> val;
  for(int i = 0; i < m; ++i){
    int v, dd, e; cin >> v >> dd >> e;
    d[v] = dd;
    w[v] = e;
  }
  T.resize(n+1);
  pre(1);
  dfs(1);
  cout << T[1]->val;
}
 
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

magictree.cpp: In member function 'void Node::range_update(int, int, int, int, long long int)':
magictree.cpp:116:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'void Node::range_update_max(int, int, int, int, long long int)':
magictree.cpp:133:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'long long int Node::get(int, int, int)':
magictree.cpp:142:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In function 'int main()':
magictree.cpp:225:15: warning: unused variable 'aa' [-Wunused-variable]
  225 |   int tt = 1, aa;
      |               ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5552 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 265812 KB Output is correct
2 Correct 111 ms 97888 KB Output is correct
3 Correct 780 ms 680168 KB Output is correct
4 Correct 358 ms 315068 KB Output is correct
5 Correct 363 ms 316940 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5976 KB Output is correct
4 Correct 77 ms 47908 KB Output is correct
5 Correct 80 ms 47564 KB Output is correct
6 Correct 109 ms 47560 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5552 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Incorrect 276 ms 223368 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15708 KB Output is correct
2 Correct 32 ms 22352 KB Output is correct
3 Correct 48 ms 22296 KB Output is correct
4 Correct 49 ms 25168 KB Output is correct
5 Correct 18 ms 18652 KB Output is correct
6 Correct 32 ms 20820 KB Output is correct
7 Correct 27 ms 21844 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5552 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 2 ms 5976 KB Output is correct
13 Correct 77 ms 47908 KB Output is correct
14 Correct 80 ms 47564 KB Output is correct
15 Correct 109 ms 47560 KB Output is correct
16 Incorrect 276 ms 223368 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 1 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 1 ms 5552 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 285 ms 265812 KB Output is correct
11 Correct 111 ms 97888 KB Output is correct
12 Correct 780 ms 680168 KB Output is correct
13 Correct 358 ms 315068 KB Output is correct
14 Correct 363 ms 316940 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5976 KB Output is correct
18 Correct 77 ms 47908 KB Output is correct
19 Correct 80 ms 47564 KB Output is correct
20 Correct 109 ms 47560 KB Output is correct
21 Incorrect 213 ms 181684 KB Output isn't correct
22 Halted 0 ms 0 KB -