Submission #943933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
943933	2024-03-12T04:56:22 Z	vjudge1	Transport (COCI19_transport)	C++17	Compilation error	0 ms	0 KB

transport

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define double long double
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=1e5+5;
vector<pii>g[N];
ll sz[N],d[N],dp[N],dpf[N],a[N];
bool vis[N]{0};
vector<ll>anc[N],aa[N];
int getsize(int u,int p){
    sz[u]=1;
    for(auto v:g[u])if(v.f!=p&&!vis[v.f])sz[u]+=getsize(v.f,u);
    return sz[u];
}
int getct(int u,int p,int req){
    for(auto v:g[u]){
        if(v.f!=p&&!vis[v.f]&&sz[v.f]*2>req)return getct(v.f,u,req);
    }return u;
}
void getd(int u,int p){
    for(auto v:g[u]){
        if(v.f==p||vis[v.f])continue;
        d[v.f] = d[u]-v.s+a[v.f];
        getd(v.f,u);
    }
}

void getdp(int u,int p,int x){
    for(auto v:g[u]){
        if(v.f==p||vis[v.f])continue;
        dp[v.f] = min(dp[u],d[v.f]-a[v.f]);
        getdp(v.f,u,x);
    }anc[x].pb(-dp[u]);
}
vector<int>fw[N];
void add(int i,int j,int amt){
    j=upper_bound(anc[i].begin(),anc[i].end(),j)-anc[i].begin();
    for(;j<fw[i].size();j+=j&-j)fw[i][j]+=amt;
}
int qr(int i,int j,int res=0){
    j=upper_bound(anc[i].begin(),anc[i].end(),j)-anc[i].begin();
    for(;j;j-=j&-j)res+=fw[i][j];
    return res;
}ll ans=0;
void solve(int u,int p,int x,int mx){
    add(x,-dp[u],-1);
    if(d[u]>=mx)aa[x].pb(u);
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        solve(v.f,u,x,max(mx,d[u]));
    }
}
void resolve(int u,int p,int x){
    add(x,-dp[u],1);
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        resolve(v.f,u,x);
    }
}
void play(int u){
    u = getct(u,u,getsize(u,u));
    vis[u]=1;d[u]=a[u];getd(u,u);
    dp[u] = 0;getdp(u,u,u);
    sort(anc[u].begin(),anc[u].end());
    fw[u].resize(anc[u].size()+2);
    for(auto it : anc[u])add(u,it,1);
    add(u,-dp[u],-1);
    ans += qr(u,d[u]-a[u]);
    add(u,-dp[u],1);
    for(auto v:g[u]){
        if(vis[v.f])continue;
        solve(v.f,u,u,a[u]);
        for(auto it : aa[u]){
            ans += qr(u,d[it]-a[u]);
        }aa[u].clear();
        resolve(v.f,u,u);
    }
    for(auto v:g[u]){
        if(vis[v.f])continue;
        play(v.f);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1,u,v,w;i<=n-1;i++){
        cin>>u>>v>>w;g[u].pb({v,w});g[v].pb({u,w});
    }play(1);cout<<ans;
}
//go_dp[u] = max(W[i],d[u]);
//from_dp[u] = min(d[u]-d[lca],w[i]);

Compilation message

transport.cpp: In function 'void add(int, int, int)':
transport.cpp:47:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(;j<fw[i].size();j+=j&-j)fw[i][j]+=amt;
      |          ~^~~~~~~~~~~~~
transport.cpp: In function 'void solve(int, int, int, int)':
transport.cpp:59:34: error: no matching function for call to 'max(int&, long long int&)'
   59 |         solve(v.f,u,x,max(mx,d[u]));
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from transport.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
transport.cpp:59:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   59 |         solve(v.f,u,x,max(mx,d[u]));
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from transport.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
transport.cpp:59:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   59 |         solve(v.f,u,x,max(mx,d[u]));
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
transport.cpp:59:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   59 |         solve(v.f,u,x,max(mx,d[u]));
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from transport.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
transport.cpp:59:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   59 |         solve(v.f,u,x,max(mx,d[u]));
      |                                  ^