oj.uz

Submission #943934

# Submission time Handle Problem Language Result Execution time Memory
943934 2024-03-12T04:56:57 Z vjudge1 Transport (COCI19_transport) C++17
130 / 130
 323 ms 52928 KB 
#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

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.0 / 13.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14940 KB Output is correct
2 Correct 16 ms 15580 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 30672 KB Output is correct
2 Correct 94 ms 29068 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 34840 KB Output is correct
2 Correct 182 ms 40208 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 45516 KB Output is correct
2 Correct 288 ms 52928 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20892 KB Output is correct
2 Correct 43 ms 18128 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 21704 KB Output is correct
2 Correct 131 ms 23864 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 27460 KB Output is correct
2 Correct 202 ms 27336 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 31680 KB Output is correct
2 Correct 258 ms 31176 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 42700 KB Output is correct
2 Correct 305 ms 39116 KB Output is correct