oj.uz

Submission #920950

# Submission time Handle Problem Language Result Execution time Memory
920950 2024-02-03T08:19:46 Z ttamx Transport (COCI19_transport) C++14
130 / 130
 217 ms 22468 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;

const int N=1e5+5;
const int M=2e5+5;

struct fenwick{
    int t[M];
    void update(int i,int v){
        for(;i<M;i+=i&-i)t[i]+=v;
    }
    int query(int i){
        int res=0;
        for(;i;i-=i&-i)res+=t[i];
        return res;
    }
}f;

int n;
ll a[N];
vector<pl> adj[N];
int sz[N];
bool used[N];
ll ans;

struct Info{
    ll need,spare;
    Info():need(0),spare(0){}
    Info(ll _need,ll _spare):need(_need),spare(_spare){}
    friend Info operator+(Info lhs,Info rhs){
        ll used=min(lhs.spare,rhs.need);
        lhs.spare-=used;
        rhs.need-=used;
        return Info(lhs.need+rhs.need,lhs.spare+rhs.spare);
    }
}dp_st[N],dp_ed[N];

int get_sz(int u,int p=0){
    sz[u]=1;
    for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=get_sz(v,u);
    return sz[u];
}

int centroid(int u,int cnt,int p=0){
    for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]>cnt)return centroid(v,cnt,u);
    return u;
}

void dfs_st(int u,int p,vector<ll> &vec){
    if(dp_st[u].need==0)vec.emplace_back(dp_st[u].spare);
    for(auto [v,w]:adj[u])if(v!=p&&!used[v]){
        dp_st[v]=Info(max(0LL,w-a[v]),max(0LL,a[v]-w))+dp_st[u];
        dfs_st(v,u,vec);
    }
}

void dfs_ed(int u,int p,vector<ll> &vec){
    vec.emplace_back(dp_ed[u].need);
    for(auto [v,w]:adj[u])if(v!=p&&!used[v]){
        dp_ed[v]=dp_ed[u]+Info(w,a[v]);
        dfs_ed(v,u,vec);
    }
}

void decom(int u){
    u=centroid(u,get_sz(u)/2);
    used[u]=true;
    vector<vector<ll>> st,ed;
    vector<ll> val{a[u]};
    for(auto [v,w]:adj[u])if(!used[v]){
        st.push_back({});
        ed.push_back({});
        dp_st[v]=Info(max(0LL,w-a[v]),max(0LL,a[v]-w)+a[u]);
        dp_ed[v]=Info(w,a[v]);
        dfs_st(v,u,st.back());
        dfs_ed(v,u,ed.back());
        for(auto x:st.back())val.emplace_back(x);
    }
    sort(val.begin(),val.end());
    auto get=[&](ll x){
        return lower_bound(val.begin(),val.end(),x)-val.begin()+1;
    };
    int cnt=0;
    for(auto &v:st)for(auto &x:v){
        x=get(x);
        f.update(x,1);
        cnt++;
    }
    ans+=cnt++;
    f.update(get(a[u]),1);
    int m=st.size();
    for(int i=0;i<m;i++){
        for(auto x:st[i])f.update(x,-1),cnt--;
        for(auto x:ed[i])ans+=cnt-f.query(get(x)-1);
        for(auto x:st[i])f.update(x,1),cnt++;
    }
    f.update(get(a[u]),-1);
    for(auto &v:st)for(auto &x:v)f.update(x,-1);
    for(auto [v,w]:adj[u])if(!used[v])decom(v);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    decom(1);
    cout << ans << "\n";
}

Compilation message

transport.cpp: In function 'int get_sz(int, int)':
transport.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=get_sz(v,u);
      |              ^
transport.cpp: In function 'int centroid(int, int, int)':
transport.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]>cnt)return centroid(v,cnt,u);
      |              ^
transport.cpp: In function 'void dfs_st(int, int, std::vector<long long int>&)':
transport.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v]){
      |              ^
transport.cpp: In function 'void dfs_ed(int, int, std::vector<long long int>&)':
transport.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v]){
      |              ^
transport.cpp: In function 'void decom(int)':
transport.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [v,w]:adj[u])if(!used[v]){
      |              ^
transport.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for(auto [v,w]:adj[u])if(!used[v])decom(v);
      |              ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7000 KB Output is correct
2 Correct 5 ms 7256 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7260 KB Output is correct
2 Correct 7 ms 7512 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 14220 KB Output is correct
2 Correct 62 ms 12856 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 16808 KB Output is correct
2 Correct 90 ms 17296 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 20428 KB Output is correct
2 Correct 126 ms 22468 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9972 KB Output is correct
2 Correct 28 ms 9308 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11668 KB Output is correct
2 Correct 74 ms 10880 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 13032 KB Output is correct
2 Correct 100 ms 12860 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 15008 KB Output is correct
2 Correct 137 ms 14792 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 18104 KB Output is correct
2 Correct 166 ms 16212 KB Output is correct