oj.uz

Submission #943659

# Submission time Handle Problem Language Result Execution time Memory
943659 2024-03-11T17:42:13 Z kim Transport (COCI19_transport) C++17
130 / 130
 246 ms 18128 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define eb emplace_back
using ll=long long;
#define sz(x) (int)(x).size()
 
vector<pair<int,ll>> adj[100005];
ll a[100005],ans;
int sz[100005];
bitset<100005> vis;
 
struct fenwick{
    vector<int> bit;
    void init(int n){bit.assign(n,0);}
    void upd(int i,int x){
        for(;i<sz(bit);i+=i&-i) bit[i]+=x;
    }
    ll qr(int i){
        ll ret=0;
        for(;i>0;i-=i&-i) ret+=bit[i];
        return ret;
    }
}fw;
 
int dfs_sz(int u,int p){
    sz[u]=1;
    for(auto &[v,w]:adj[u]){
        if(!vis[v]&&v!=p) sz[u]+=dfs_sz(v,u);
    }
    return sz[u];
}
int centroid(int u,int p,int n){
    for(auto &[v,w]:adj[u]){
        if(!vis[v]&&v!=p&&sz[v]>n) return centroid(v,u,n);
    }
    return u;
}
void dfs1(int u,int p,ll sum,ll mx,vector<ll> &vec){
    if(sum>=mx) vec.eb(sum);
    for(auto &[v,w]:adj[u]){
        if(vis[v]||v==p) continue;
        dfs1(v,u,sum+a[v]-w,max(mx,sum+a[v]-w),vec);
    }
}
void dfs2(int u,int p,ll sum,ll mx,vector<ll> &vec){
    vec.eb(mx);
    for(auto &[v,w]:adj[u]){
        if(vis[v]||v==p) continue;
        dfs2(v,u,sum+w-a[u],max(mx,sum+w-a[u]),vec);
    }
}
void decomp(int u){
    int c=centroid(u,u,dfs_sz(u,u)>>1);
    vis[c]=1;
 
    ll x=ans;
 
    vector<vector<ll>> v1,v2;
    vector<ll> comp;
    for(auto &[v,w]:adj[c]){
        if(vis[v]) continue;
        vector<ll> tmp1,tmp2;
        dfs1(v,c,a[v]-w,max(0LL,a[v]-w),tmp1);
        dfs2(v,c,w-a[c],w-a[c],tmp2);
        v1.eb(tmp1), v2.eb(tmp2);
        for(auto &e:tmp2){
            comp.eb(e);
            if(e<=0) ++ans;
        }
        ans+=sz(tmp1);
    }
 
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    
    fw.init(sz(comp)+5);
    for(int i=0;i<sz(v1);++i){
        for(auto &e:v1[i]) ans+=fw.qr(upper_bound(comp.begin(),comp.end(),e)-comp.begin());
        for(auto &e:v2[i]) fw.upd(lower_bound(comp.begin(),comp.end(),e)-comp.begin()+1,1);
    }
    fw.init(sz(comp)+5);
    for(int i=sz(v1)-1;i>=0;--i){
        for(auto &e:v1[i]) ans+=fw.qr(upper_bound(comp.begin(),comp.end(),e)-comp.begin());
        for(auto &e:v2[i]) fw.upd(lower_bound(comp.begin(),comp.end(),e)-comp.begin()+1,1);
    }
    
    for(auto &[v,w]:adj[c]){
        if(!vis[v]) decomp(v);
    }
}
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n; cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<n;++i){
        int u,v; cin>>u>>v;
        ll w; cin>>w;
        adj[u].eb(v,w), adj[v].eb(u,w);
    }
    decomp(1);
    cout<<ans;
 
    return 0;
}

Compilation message

transport.cpp: In function 'void decomp(int)':
transport.cpp:57:8: warning: unused variable 'x' [-Wunused-variable]
   57 |     ll x=ans;
      |        ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3928 KB Output is correct
2 Correct 6 ms 4184 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 10720 KB Output is correct
2 Correct 69 ms 10672 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 12672 KB Output is correct
2 Correct 118 ms 15452 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 16156 KB Output is correct
2 Correct 189 ms 18128 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6812 KB Output is correct
2 Correct 34 ms 6532 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7912 KB Output is correct
2 Correct 106 ms 8896 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 8952 KB Output is correct
2 Correct 137 ms 10832 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 10752 KB Output is correct
2 Correct 176 ms 12620 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 13576 KB Output is correct
2 Correct 246 ms 14764 KB Output is correct