Submission #943205

#	Time	Username	Problem	Language	Result	Execution time	Memory
943205		Warinchai	Transport (COCI19_transport)	C++14	130 / 130	457 ms	21896 KiB

Main

#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 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13