This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
const int nmax = 1e5;
int in[nmax + 5], out[nmax + 5], timer = 0;
vector < int > adj[nmax + 5];
vector < pii > fruits[nmax + 5];
struct SegTree {
int n;
bool del[nmax * 4 + 5];
ll b[nmax * 4 + 5];
void init(int _n) {
n = _n;
}
void down(int id) {
if (!del[id]) {
return;
}
del[id << 1] = 1;
del[id << 1 | 1] = 1;
b[id << 1] = 0;
b[id << 1 | 1] = 0;
del[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val) {
if (l > v || u > r) {
return;
}
if (u <= l && r <= v) {
if (val != -1) {
b[id] = val;
}
else {
del[id] = 1;
b[id] = 0;
}
return;
}
down(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
b[id] = b[id << 1] + b[id << 1 | 1];
}
ll get(int id, int l, int r, int u, int v) {
if (u > r || l > v) {
return 0;
}
if (u <= l && r <= v) {
return b[id];
}
down(id);
int mid = (l + r) >> 1;
return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}
void update(int l, int r, int val) {
update(1, 1, n, l, r, val);
// cout << l << " " << r << " " << val << "\n";
}
ll get(int l, int r) {
return get(1, 1, n, l, r);
}
}seg;
void dfs(int i) {
in[i] = ++ timer;
for (auto x: adj[i]) {
dfs(x);
}
out[i] = timer;
}
signed main() {
if (fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
seg.init(n);
FOR(i, 2, n) {
int p;
cin >> p;
adj[p].push_back(i);
}
dfs(1);
for (; m --;) {
int v, d, w;
cin >> v >> d >> w;
fruits[d].push_back({v, w});
}
FORD(i, k, 1) {
sort(fruits[i].begin(), fruits[i].end(), [&] (const pii &x, const pii &y) {
return (in[x.fi] < in[x.se]);
});
for (auto x: fruits[i]) {
int u = x.fi;
if (seg.get(in[u], out[u]) <= x.se) {
seg.update(in[u], out[u], -1);
seg.update(in[u], out[u], x.se);
}
}
}
cout << seg.b[1];
return 0;
}
Compilation message (stderr)
magictree.cpp: In function 'int main()':
magictree.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |