oj.uz

Submission #855627

# Submission time Handle Problem Language Result Execution time Memory
855627 2023-10-01T14:24:10 Z mychecksedad Magic Tree (CEOI19_magictree) C++17
14 / 100
 629 ms 439568 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;
        }
        if(lazy2 > R->val){
          R->val = max(lazy2, R->val);
          R->lazy2 = max(lazy2, R->lazy2);
          R->settime = settime;
        }
        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;
          }
          if(lazy2 > R->val){
            R->val = max(lazy2, R->val);
            R->lazy2 = max(lazy2, R->lazy2);
            R->settime = settime;
          }
          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->settime = settime;
          }
          if(lazy2 > R->val){
            R->val = max(lazy2, R->val);
            R->lazy2 = max(lazy2, R->lazy2);
            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){
      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){
      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:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'void Node::range_update_max(int, int, int, int, long long int)':
magictree.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'long long int Node::get(int, int, int)':
magictree.cpp:132:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In function 'int main()':
magictree.cpp:215:15: warning: unused variable 'aa' [-Wunused-variable]
  215 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Incorrect 2 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 170164 KB Output is correct
2 Correct 104 ms 71244 KB Output is correct
3 Correct 629 ms 439568 KB Output is correct
4 Correct 260 ms 215504 KB Output is correct
5 Correct 308 ms 217056 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 3 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 85 ms 43032 KB Output is correct
5 Correct 69 ms 43464 KB Output is correct
6 Correct 102 ms 43336 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 116472 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 Incorrect 2 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Incorrect 2 ms 5724 KB Output isn't correct
3 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 Incorrect 2 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -