이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5 + 5;
#define lc ind<<1
#define rc ind<<1|1
struct Node { //range add, range set, some kind of walking
long long mx,alz,slz;
Node () {mx = alz = 0; slz = -1;}
} tree[MN << 2];
void push_down (int ind, int l, int r) {
if (tree[ind].slz >= 0) {
tree[ind].mx = tree[ind].slz;
if (l != r) {
tree[lc].slz = tree[rc].slz = tree[ind].slz;
tree[lc].alz = tree[rc].alz = 0;
}
tree[ind].slz = -1;
}
if (tree[ind].alz) {
tree[ind].mx += tree[ind].alz;
if (l != r) {
tree[lc].alz += tree[ind].alz;
tree[rc].alz += tree[ind].alz;
}
tree[ind].alz = 0;
}
}
void update (int ind, int tl, int tr, int l, int r, long long v) {
push_down(ind,tl,tr);
if (tl > r || tr < l) return;
if (l <= tl && tr <= r) {
tree[ind].alz += v;
push_down(ind,tl,tr);
return;
}
int mid = (tl + tr) / 2;
update(lc,tl,mid,l,r,v); update(rc,mid+1,tr,l,r,v);
tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
int walk (int ind, int tl, int tr, long long v) {
push_down(ind,tl,tr);
if (tl == tr) return tree[ind].mx > v ? tl : -1;
int mid = (tl + tr) / 2;
push_down(lc,tl,mid);
if (tree[lc].mx > v) return walk(lc,tl,mid,v);
return walk(rc,mid+1,tr,v);
}
void setv (int ind, int tl, int tr, int l, int r, long long v) {
push_down(ind,tl,tr);
if (tl > r || tr < l) return;
if (l <= tl && tr <= r) {
tree[ind].slz = v; tree[ind].alz = 0;
push_down(ind,tl,tr);
return;
}
int mid = (tl + tr) / 2;
setv(lc,tl,mid,l,r,v); setv(rc,mid+1,tr,l,r,v);
tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
long long query (int ind, int tl, int tr, int i) {
push_down(ind,tl,tr);
if (tl == tr) return tree[ind].mx;
int mid = (tl + tr) / 2;
if (i <= mid) return query(lc,tl,mid,i);
return query(rc,mid+1,tr,i);
}
int a[MN], h[MN], c[MN], sz[MN], st[MN], ed[MN], at[MN], big[MN], tt;
vector<int> adj[MN], xs;
int getx (int x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
void getsz (int cur) {
sz[cur] = 1; st[cur] = ++tt; at[tt] = cur;
for (int i : adj[cur]) {
getsz(i);
sz[cur] += sz[i];
if (sz[i] > sz[big[cur]]) big[cur] = i;
}
ed[cur] = tt;
}
vector<pair<int,long long>> dp[MN];
void dfs (int cur, bool del = false) {
for (int i : adj[cur]) if (i != big[cur]) dfs(i,true);
if (big[cur]) dfs(big[cur],false);
for (int i : adj[cur]) if (i != big[cur]) {
int lst = 1;
for (auto [j,v] : dp[i]) {
if (lst <= j) update(1,1,(int)xs.size(),lst,j,v);
lst = j+1;
}
}
update(1,1,(int)xs.size(),1,(int)xs.size(),c[cur]);
long long getv = query(1,1,(int)xs.size(),h[cur])-c[cur];
int pos = walk(1,1,(int)xs.size(),getv);
if (pos <= h[cur]) setv(1,1,(int)xs.size(),pos,h[cur],getv);
if (del) {
vector<int> hs;
for (int j = st[cur]; j <= ed[cur]; j++) hs.push_back(h[at[j]]);
hs.push_back((int)xs.size());
sort(hs.begin(),hs.end());
hs.erase(unique(hs.begin(),hs.end()),hs.end());
dp[cur].resize(hs.size());
for (int i = 0; i < (int)hs.size(); i++) dp[cur][i] = {hs[i],query(1,1,(int)xs.size(),hs[i])};
tree[1].slz = tree[1].alz = 0;
}
}
int main () {
int n; scanf ("%d",&n);
for (int i = 1; i <= n; i++) {
scanf ("%d %d %d",&a[i],&h[i],&c[i]);
xs.push_back(h[i]);
if (i > 1) adj[a[i]].push_back(i);
}
sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
for (int i = 1; i <= n; i++) h[i] = getx(h[i]);
getsz(1);
dfs(1);
long long ret = 1e18;
for (auto [j,v] : dp[1]) ret = min(ret,v);
printf ("%lld\n",query(1,1,(int)xs.size(),1));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:106:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
106 | int n; scanf ("%d",&n);
| ~~~~~~^~~~~~~~~
worst_reporter2.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
108 | scanf ("%d %d %d",&a[i],&h[i],&c[i]);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |