oj.uz

Submission #855583

# Submission time Handle Problem Language Result Execution time Memory
855583 2023-10-01T13:25:07 Z mychecksedad Magic Tree (CEOI19_magictree) C++17
32 / 100
 559 ms 441908 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){
        L->val = max(lazy2, L->val);
        R->val = max(lazy2, R->val);
        L->lazy2 = max(lazy2, L->lazy2);
        R->lazy2 = max(lazy2, R->lazy2);
        L->settime = settime;
        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){
          L->val = max(lazy2, L->val);
          R->val = max(lazy2, R->val);
          L->lazy2 = max(lazy2, L->lazy2);
          R->lazy2 = max(lazy2, R->lazy2);
          L->settime = settime;
          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;

          L->val = max(lazy2, L->val);
          R->val = max(lazy2, R->val);
          L->lazy2 = max(lazy2, L->lazy2);
          R->lazy2 = max(lazy2, R->lazy2);
          L->settime = settime;
          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 << max(T[1]->val, d[1] == 0 ? 0ll : T[1]->get(1, M, d[1]) + w[1]);
}
 
 
 
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:96:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'void Node::range_update_max(int, int, int, int, long long int)':
magictree.cpp:111:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In member function 'long long int Node::get(int, int, int)':
magictree.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |     int m = l+r>>1;
      |             ~^~
magictree.cpp: In function 'int main()':
magictree.cpp:203:15: warning: unused variable 'aa' [-Wunused-variable]
  203 |   int tt = 1, aa;
      |               ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 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 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 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 212 ms 170068 KB Output is correct
2 Correct 89 ms 72016 KB Output is correct
3 Correct 559 ms 441908 KB Output is correct
4 Correct 249 ms 217560 KB Output is correct
5 Correct 273 ms 219352 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 5980 KB Output is correct
4 Correct 66 ms 41412 KB Output is correct
5 Correct 67 ms 41420 KB Output is correct
6 Correct 86 ms 41504 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 114508 KB Output is correct
2 Correct 134 ms 113744 KB Output is correct
3 Correct 85 ms 57832 KB Output is correct
4 Correct 185 ms 209356 KB Output is correct
5 Correct 52 ms 29820 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 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 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Incorrect 183 ms 130132 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12376 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 5720 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 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 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 5980 KB Output is correct
13 Correct 66 ms 41412 KB Output is correct
14 Correct 67 ms 41420 KB Output is correct
15 Correct 86 ms 41504 KB Output is correct
16 Incorrect 183 ms 130132 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 5720 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 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 212 ms 170068 KB Output is correct
11 Correct 89 ms 72016 KB Output is correct
12 Correct 559 ms 441908 KB Output is correct
13 Correct 249 ms 217560 KB Output is correct
14 Correct 273 ms 219352 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 5980 KB Output is correct
18 Correct 66 ms 41412 KB Output is correct
19 Correct 67 ms 41420 KB Output is correct
20 Correct 86 ms 41504 KB Output is correct
21 Correct 165 ms 114508 KB Output is correct
22 Correct 134 ms 113744 KB Output is correct
23 Correct 85 ms 57832 KB Output is correct
24 Correct 185 ms 209356 KB Output is correct
25 Correct 52 ms 29820 KB Output is correct
26 Incorrect 183 ms 130132 KB Output isn't correct
27 Halted 0 ms 0 KB -