Submission #914976

#	Time	Username	Problem	Language	Result	Execution time	Memory
914976		winter0101	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	1473 ms	102072 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const long long inf=1e18;
const int maxn=2e5+9;
struct node{
long long val,lazy;
node(){
val=lazy=0;
}
};
node cmp(const node &p,const node &q){
node r;
r.val=max(p.val,q.val);
return r;
}
struct IT{
vector<node>st;
void resz(int n){
st.resize(4*n+9);
}
void push(int id){
if (st[id].lazy){
st[id<<1].val+=st[id].lazy;
st[id<<1|1].val+=st[id].lazy;
st[id<<1].lazy+=st[id].lazy;
st[id<<1|1].lazy+=st[id].lazy;
st[id].lazy=0;
}
}
void update(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id].lazy+=val;
st[id].val+=val;
return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=cmp(st[id<<1],st[id<<1|1]);
}
long long get(int id,int l,int r,int u){
if (r<u)return inf;
while (true){
if (l==r)return st[id].val;
push(id);
int mid=(l+r)>>1;
if (mid>=u){
id=(id<<1);
r=mid;
}
else {
id=(id<<1|1);
l=mid+1;
}
}
return 0;
}
int walk(int id,int l,int r,long long val){
if (st[id].val<val)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
push(id);
if (st[id<<1].val>=val)return walk(id<<1,l,mid,val);
else return walk(id<<1|1,mid+1,r,val);
}
};
vector<int>a[maxn];
int h[maxn];
long long c[maxn];
int par[maxn];
struct type{
int l,r;
long long val;
};
vector<type>b[maxn];
int sub[maxn];
vector<int>vertice[maxn];
void predfs(int u){
sub[u]=sz(vertice[u]);
for (auto &v:a[u]){
predfs(v);
sub[u]+=sub[v];
if (sub[v]>sub[a[u][0]])swap(a[u][0],v);
}
}
int n,m;
IT st;
int deg[maxn];
long long sum[maxn];
void dfs(int u){
if (!a[u].empty()){
for (auto v:a[u]){
if (v==a[u][0])continue;
dfs(v);
int pointer=m;
while (pointer){
type tmp;
tmp.val=st.get(1,1,m,pointer);
tmp.r=pointer;
tmp.l=st.walk(1,1,m,tmp.val);
b[v].pb(tmp);
pointer=tmp.l-1;
}
for (auto x:b[v]){
st.update(1,1,m,x.l,x.r,-x.val);
}
}
dfs(a[u][0]);
for (auto v:a[u]){
if (v==a[u][0])continue;
for (auto x:b[v]){
st.update(1,1,m,x.l,x.r,x.val);
}
vector<type>().swap(b[v]);
}
}
vector<int>xd;
long long ss=0;
for (auto v:vertice[u]){
sum[h[v]]+=c[v];
ss+=c[v];
xd.pb(h[v]);
}
xd.pb(0);
sort(all(xd));
xd.resize(distance(xd.begin(),unique(all(xd))));
for (auto v:xd)sum[v]=ss-sum[v];
st.update(1,1,m,xd.back()+1,m,ss);
for2(i,sz(xd)-1,1){
long long hjhj=st.get(1,1,m,xd[i]+1);
long long val=st.get(1,1,m,xd[i]);
if (hjhj<val+sum[xd[i]]){
st.update(1,1,m,xd[i],xd[i],-val+hjhj);
val=hjhj;
}
else {
val+=sum[xd[i]];
st.update(1,1,m,xd[i],xd[i],sum[xd[i]]);
}
int l=xd[i-1]+1,r=xd[i]-1;
while (l<=r){
long long vl=st.get(1,1,m,r);
if (vl+ss<=val)break;
int pos=st.walk(1,1,m,vl);
if (pos<l)pos=l;
st.update(1,1,m,pos,r,-vl+val);
r=pos-1;
}
st.update(1,1,m,l,r,ss);
}
for (auto v:xd)sum[v]=0;
}
bool vis[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n;
    vector<int>nn;
    nn.pb(1);
    for1(i,1,n){
    int p;
    cin>>p;
    par[i]=p;
    cin>>h[i]>>c[i];
    nn.pb(h[i]);
    }
    sort(all(nn));
    nn.resize(distance(nn.begin(),unique(all(nn))));
    m=sz(nn);
    map<int,int>nenso;
    for1(i,0,sz(nn)-1){
    nenso[nn[i]]=i+1;
    }
    for1(i,1,n)h[i]=nenso[h[i]];
    h[0]=1;
    st.resz(m);
    for1(i,1,n){
    deg[par[i]]++;
    }
    queue<int>dag;
    for1(i,1,n)if (!deg[i])dag.push(i);
    while (!dag.empty()){
    auto u=dag.front();
    dag.pop();
    deg[par[u]]--;
    if (!deg[par[u]])dag.push(par[u]);
    }
    for1(i,1,n)if (par[i]!=i&&!deg[i])a[par[i]].pb(i);
    for1(i,1,n)vertice[i].pb(i);
    for1(i,1,n){
    if (vis[i]||!deg[i])continue;
    int u=i;
    vector<int>xd;
    while (true){
    if (vis[u])break;
    xd.pb(u);
    vis[u]=1;
    u=par[u];
    }
    u=xd.back();
    a[0].pb(u);
    xd.pop_back();
    for (auto v:xd){
    vertice[u].pb(v);
    vertice[v].clear();
    for (auto x:a[v]){
    a[u].pb(x);
    }
    vector<int>().swap(a[v]);
    }
    }
    predfs(0);
    dfs(0);
    cout<<st.get(1,1,m,1);
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21