oj.uz

Submission #938919

# Submission time Handle Problem Language Result Execution time Memory
938919 2024-03-05T20:21:52 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
14 / 100
 193 ms 25052 KB 
/*adid_r10*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//#define int long long
const int N = 1e5 + 9, MOD = 1e9 + 7;
    
//// Total Code time complexity: O(nlogn)



////
    
int n, m, k;
struct ST {
  int t[4 * N];
  static const int inf = 1e9;
  ST() {
    memset(t, 0, sizeof t);
  }
  void upd(int _n, int b, int e, int i, int x) {
    if (b > i || e < i) return;
    if (b == e && b == i) {
      t[_n] = x; // update
      return;
    }
    int mid = (b + e) >> 1, l = _n << 1, r = l | 1;
    upd(l, b, mid, i, x);
    upd(r, mid + 1, e, i, x);
    t[_n] = max(t[l], t[r]); // change this
  }
  void upd (int idx, int x) {
    upd(1, 1, n, idx, x);
  }

  int query(int _n, int b, int e, int i, int j) {
    if (b > j || e < i) return 0; // return appropriate value
    if (b >= i && e <= j) return t[_n];
    int mid = (b + e) >> 1, l = _n << 1, r = l | 1;
    return max(query(l, b, mid, i, j), query(r, mid + 1, e, i, j)); // change this
  }
  int query(int l, int r) {
    return query (1, 1, n, l, r);
  }
};
///

vector <int> adj[N];
int sz[N];

int TM = 1;
int st [N], ft[N], node_start[N];
void dfsz_and_eulerTour (int u, int p) {
    sz[u] = 1;
    node_start[TM] = u;
    st[u] = TM++;
    for (auto v: adj[u]) {
        if (v != p) {
            dfsz_and_eulerTour (v, u);
            sz[u] += sz[v];
        }
    }
    ft[u] = TM;
}
int dd[N], ww[N];
void ddffss (int u, int p, ST &seg) {

    for (auto v: adj[u]) {
        if (v != p) {
            ddffss(v, u, seg);
        }
    }
    seg.upd(dd[u], seg.query(0, dd[u]) + ww[u]);
}

ll ans[N];
void dfs (int u, int p, bool keep, ST &seg) {
    int mxsz = -1, bigchild = -1;
    for (auto v: adj[u]) {
        if (v != p) {
            if (sz[v] > mxsz) {
                mxsz = sz[v];
                bigchild = v;
            }
        
        }
    }

    for (auto v: adj[u]) {
        if (v != p && v != bigchild) {
            dfs(v, u, 0, seg);
            ans[u] += ans[v];
        }
    }
    if (bigchild != -1) {
        dfs(bigchild, u, 1, seg);
        ans[u] += ans[bigchild];
    }
    
    for (auto v: adj[u]) {
        if (v != p && v != bigchild) {
            // for (int t = st[v]; t < ft[v]; t++) {
            //     // OPS(node_start[t], mxfrq, sum);
            //     // colcnt[col[node_start[t]]]++;

            // }
            ddffss (v, p, seg);
        } 
    }

    seg.upd(dd[u], seg.query (0, dd[u]) + ww[u]);
    ans[u] = max(ans[u], 1LL * seg.query (0, dd[u]));
    // OPS(u, mxfrq, sum);
    // colcnt[col[u]]++;    
    //now colcnt[c] is the number of vertices in subtree of vertex u that has color c. You can answer the queries 

    if (keep == 0) {
        for (int t = st[u]; t < ft[u]; t++) {
            int cc = node_start[t];
            // colcnt[col[cc]]--;
            seg.upd(dd[cc], 0);
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int nn;
    cin >> nn >> m >> k;
    n = k;
    ST seg;
    for (int i = 2; i <= nn; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
    }   

    for (int i = 1; i <= m; i++) {
        int v, d, w; cin >> v >> d >> w;
        dd[v] = d;
        ww[v] = w;
    }
    dfsz_and_eulerTour(1, -1);
    dfs (1, -1, 0, seg);
    cout << ans[1] << '\n';
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7320 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9808 KB Output is correct
2 Correct 46 ms 15952 KB Output is correct
3 Correct 193 ms 10640 KB Output is correct
4 Correct 96 ms 10020 KB Output is correct
5 Correct 113 ms 11976 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 3 ms 7256 KB Output is correct
3 Correct 3 ms 7332 KB Output is correct
4 Correct 63 ms 24952 KB Output is correct
5 Correct 65 ms 25052 KB Output is correct
6 Correct 81 ms 25028 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7320 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7320 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 3 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7320 KB Output isn't correct
10 Halted 0 ms 0 KB -