Submission #335383

#	Time	Username	Problem	Language	Result	Execution time	Memory
335383		mehrdad_sohrabi	Construction of Highway (JOI18_construction)	C++14	100 / 100	537 ms	33052 KiB

construction

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100;
vector <int> g[N];
vector <pii> y[N];
ll hd[N];
ll a[N],st[N],fn[N],ts=1;
ll sz[N];
ll par[N];
ll hi[N];
void dfssz(ll v,ll p){
    par[v]=p;
    sz[v]=1;
    hi[v]=hi[p]+1;
    for (auto u : g[v]){
        if (u==p) continue;
        dfssz(u,v);
        sz[v]+=sz[u];
    }
}
void dfshld(ll v,ll p,ll h){
    hd[v]=h;
    ll big=0;
    st[v]=ts;
    for (auto u : g[v]){
        if (u==p) continue;
        if (sz[u]>sz[big]) big=u;
    }
    if (big){
        ts++;
        dfshld(big,v,h);
    }
    for (auto u : g[v]){
        if (u==p || u==big) continue;
        ts++;
        dfshld(u,v,u);
    }
    fn[v]=ts;
}
ll fen[N];
void add(ll idx,ll val){
    for (;idx<N;idx+=idx & (-idx)){
        fen[idx]+=val;
    }
}
ll get(ll idx){
    ll s=0;
    for (;idx;idx-= idx & (-idx)){
        s+=fen[idx];
    }
    return s;
}
ll solve(vector <pii> t){
    ll s=0;
    for (auto u : t){
        s+=get(u.S-1)*u.F;
        add(u.S,u.F);
    }
    for (auto u : t){
        add(u.S,-u.F);
    }
    return s;
}
map <int,int> mp;
int32_t main(){
    sync;
    ll n;
    cin >> n;
    vector <int> com;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        com.pb(a[i]);
    }
    sort(com.begin(),com.end());
    for (int i=0;i<com.size();i++){
        mp[com[i]]=i+1;
    }
    for (int i=1;i<=n;i++){
        a[i]=mp[a[i]];
    }
    vector <pii> yal;
    for (int i=0;i<n-1;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        yal.pb({u,v});
    }
    dfssz(1,1);
    dfshld(1,1,1);
    par[1]=0;
    for (int i=0;i<n-1;i++){
        ll v=yal[i].S;
        ll z=v;
        vector <pii> tt,t;
        while(true){
            ll k=hd[v];
        //    cout << v << " erjf " << k << endl;
            while(y[k].size() && y[k].back().F<=hi[v]) tt.pb({y[k].back().F,y[k].back().S}),y[k].pop_back();
            if (y[k].size()) tt.pb({hi[v],y[k].back().S});
            y[k].pb({hi[v],a[z]});
            v=par[k];

            reverse(tt.begin(),tt.end());
            for (int i=0;i<(ll)tt.size()-1;i++){
                tt[i].F-=tt[i+1].F;
            }
            if (tt.size())
                tt[tt.size()-1].F-=hi[par[k]];
            for (auto u : tt) t.pb(u);
            tt.clear();
            if (k==1) break;
        }
       // reverse(t.begin(),t.end());
 //  for (auto u : t) cout << u.F << " " << u.S << "  rwegr ";
   //    cout << " mrgrtg " << endl;
       cout << solve(t) << endl;
    }
    for (int i=1;i<=n;i++){
       // cout << hd[i] << endl;
    }

}
/*
5
1 7 3 4 8
1 2
1 3
2 4
3 5
*/

Compilation message (stderr)

construction.cpp: In function 'int32_t main()':
construction.cpp:86:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0;i<com.size();i++){
      |                  ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84