oj.uz

Submission #943234

# Submission time Handle Problem Language Result Execution time Memory
943234 2024-03-11T09:31:36 Z kim Transport (COCI19_transport) C++17
0 / 130
 244 ms 17016 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){
    for(auto &[v,w]:adj[u]){
        if(vis[v]||v==p) continue;
        if(a[v]-w>=mx) vec.eb(sum+a[v]-w);
        dfs1(v,u,sum+a[v]-w,max(mx,w-a[v]+mx),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;
        if(a[v]-w>=0) tmp1.eb(a[v]-w);
        dfs1(v,c,a[v]-w,max(0LL,w-a[v]),tmp1);
        dfs2(v,u,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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 11208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 13604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 17016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 6848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 8396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 11728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 14696 KB Output isn't correct
2 Halted 0 ms 0 KB -