Submission #943934

#	Time	Username	Problem	Language	Result	Execution time	Memory
943934		vjudge1	Transport (COCI19_transport)	C++17	130 / 130	323 ms	52928 KiB

Main

#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,ll 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,ll 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,ll 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 (stderr)

transport.cpp: In function 'void add(int, long long int, int)':
transport.cpp:47:11: warning: comparison of integer expressions of different signedness: 'long long 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;
      |          ~^~~~~~~~~~~~~

• 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