oj.uz

Submission #943205

# Submission time Handle Problem Language Result Execution time Memory
943205 2024-03-11T09:17:30 Z Warinchai Transport (COCI19_transport) C++14
130 / 130
 457 ms 21896 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[100005];
vector<pair<int,int>>adj[100005];
int used[100005];
int sz[100005];
int inf=1e18+5;
struct fenwick{
    int info[200005];
    void upd(int x,int val){
        for(int i=x;i<=200000;i+=i&-i)info[i]+=val;
    }
    int fans(int x){
        int ans=0;
        for(int i=x;i>0;i-=i&-i)ans+=info[i];
        return ans;
    }
}fw;
int dfssz(int u,int p=-1){
    sz[u]=1;
    for(auto x:adj[u])if(x.first!=p&&!used[x.first])sz[u]+=dfssz(x.first,u);
    return sz[u];
}
int centroid(int u,int rsz,int p=-1){
    for(auto x:adj[u])if(x.first!=p&&!used[x.first]&&sz[x.first]>rsz/2)return centroid(x.first,rsz,u);
    return u;
}
int ans=0;
vector<int>v;
int ids[100005];
void dfsaddid(int u,int mx,int sm,int p=-1){
    //cerr<<"add id:"<<u<<" "<<mx<<"\n";
    v.push_back(mx);
    for(auto x:adj[u])if(x.first!=p&&!used[x.first]){
        int netf=ar[u]-x.second;
        dfsaddid(x.first,max(mx,-1*(sm+netf)),sm+netf,u);
    }
}
int cur=0;
void dfsans(int u,int fuel,int cst,int bpre,int p){
    int id=upper_bound(v.begin(),v.end(),fuel)-v.begin();
    //fw.upd(ids[u],-1);
    if(fuel>=0&&ar[u]>=cst&&bpre>=0)ans+=fw.fans(id);
    //cerr<<"ans:"<<u<<" "<<id<<" "<<fuel<<" "<<fw.fans(id)<<"\n";
    //if(fw.fans(id)!=0&&fuel>=0&&ar[u]>=cst&&bpre>=0)cerr<<"AANNNSSS:"<<u<<" "<<fw.fans(id)<<" "<<cur<<"\n";
    //fw.upd(ids[u],1);
    for(auto x:adj[u])if(x.first!=p&&!used[x.first]){
        int netf=fuel+ar[x.first]-x.second;
        dfsans(x.first,netf,x.second,min(0ll,bpre+ar[x.first]-x.second),u);
    }
}
void dfsadd(int u,int mx,int sm,int p=-1){
    int id=lower_bound(v.begin(),v.end(),mx)-v.begin()+1;
    ids[u]=id;
    fw.upd(id,1);
    //cerr<<"add:"<<u<<" "<<id<<' '<<mx<<"\n";
    for(auto x:adj[u])if(x.first!=p&&!used[x.first]){
        int netf=ar[u]-x.second;
        dfsadd(x.first,max(mx,-1*(sm+netf)),sm+netf,u);
    }
}
void dfsrem(int u,int mx,int sm,int p=-1){
    int id=lower_bound(v.begin(),v.end(),mx)-v.begin()+1;
    fw.upd(id,-1);
    //cerr<<"rem:"<<u<<" "<<id<<" "<<mx<<"\n";
    for(auto x:adj[u])if(x.first!=p&&!used[x.first]){
        int netf=ar[u]-x.second;
        dfsrem(x.first,max(mx,-1*(sm+netf)),sm+netf,u);
    }
}
void decom(int u){
    //cerr<<u<<"\n";
    u=centroid(u,dfssz(u),-1);
    //cerr<<"centroid:"<<u<<"\n";
    cur=u;
    used[u]=1;
    v.clear();
    dfsaddid(u,0,0);
    sort(v.begin(),v.end());
    dfsadd(u,0,0);
    for(auto x:adj[u])if(!used[x.first]){
        int netf=ar[u]-x.second;
        dfsrem(x.first,max(0ll,-1*(netf)),netf,u);
        dfsans(x.first,ar[x.first]-x.second,x.second,0,-1);
        dfsadd(x.first,max(0ll,-1*(netf)),netf,0);
    }
    //dfsans(u,ar[u],-1);
    fw.upd(ids[u],-1);
    ans+=fw.fans(1);
    //cerr<<"root add"<<fw.fans(1)<<"\n";
    //if(fw.fans(1)!=0)cerr<<"RROOTT AANNNSSS:"<<u<<" "<<fw.fans(1)<<" "<<cur<<"\n";
    fw.upd(ids[u],1);
    dfsrem(u,0,0,-1);
    //for(int i=1;i<=200000;i++)fw.info[i]=0;
    //cerr<<u<<" end\n";
    for(auto x:adj[u])if(!used[x.first])decom(x.first);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>ar[i];
    for(int i=1;i<=n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    //cerr<<"work\n";
    //fw.upd(1,1);
    decom(1);
    cout<<ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6744 KB Output is correct
2 Correct 8 ms 7040 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7016 KB Output is correct
2 Correct 14 ms 7248 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 13260 KB Output is correct
2 Correct 118 ms 12768 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 15824 KB Output is correct
2 Correct 212 ms 17348 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 19056 KB Output is correct
2 Correct 335 ms 21896 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9180 KB Output is correct
2 Correct 49 ms 8992 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10972 KB Output is correct
2 Correct 178 ms 10708 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 12288 KB Output is correct
2 Correct 243 ms 12748 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 14272 KB Output is correct
2 Correct 310 ms 14284 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 16468 KB Output is correct
2 Correct 407 ms 15824 KB Output is correct