Submission #1268892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268892		mohammadsam	Construction of Highway (JOI18_construction)	C++20	100 / 100	205 ms	17160 KiB

construction

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n ;
vector<int> g[N];
int par[N],sz[N],head[N],big[N],dis[N];
int arr[N];
struct BIT{
    int fen[N];
    vector<pii> op;
    void add(int i,int v,bool c =1){
        if(c) op.pb({i,v});
        for(;i<=n;i+=-i&i) fen[i] += v;
    }
    int ask(int i){
        int ans = 0;
        for(;i;i-=-i&i) ans += fen[i];
        return ans;
    }
    void reset(){
        for(auto [i,v] : op) add(i,-v,0);
        op.clear();
    }
}F;
void dfs(int u){
    sz[u] = 1;
    for(auto h : g[u]){
        dfs(h);
        sz[u] += sz[h];
        if(sz[h] > sz[big[u]]) big[u] = h;
    }
}
vector<pii> stk[N];
void HLD(int u,int h){
    head[u] = h;
    if(big[u]) HLD(big[u],h);
    for(auto v : g[u]){
        if(v != big[u]) HLD(v,v);
    }
}
ll ask(int u){
    ll ans = 0;
    while(u){
        int h = head[u];
        int cnt = dis[u] - dis[h] + 1;
        vector<pii> val;
        for(int j = len(stk[h]) - 1;j >= 0;j--){
            if(stk[h][j].sec <= cnt){
                val.pb(stk[h][j]);
                cnt -= stk[h][j].sec;
            }
            else{
                val.pb({stk[h][j].fi,cnt});
                break;
            }
        }
        
        reverse(all(val));
        for(auto [x,c] :  val){
            ans += c * F.ask(x-1);
            F.add(x,c);
        }
        u = par[h];
    }
    F.reset();
    return ans;
}
void update(int u,int x){
    while(u){
        int h = head[u];
        int cnt = dis[u] - dis[h] + 1;
        while(!stk[h].empty()){
            if(stk[h].back().sec <= cnt){
                cnt -= stk[h].back().sec;
                stk[h].pop_back();
            }
            else{
                stk[h].back().sec -= cnt;
                break;
            }
        }
        stk[h].pb({x,dis[u] - dis[h] + 1});
        u = par[h];
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n;
    for(int i=1 ;i <= n;i++) cin >> arr[i];
    vector<pii> E;
    for(int i = 0; i < n - 1;i++){
        int a,b;
        cin >> a >> b ;
        par[b] = a;
        dis[b] = dis[a] + 1;
        E.pb({a,b});
        g[a].pb(b);
    }
    vector<int> cmp;
    for(int i =1;i <= n;i++) cmp.pb(arr[i]);
    sort(all(cmp));
    cmp.resize(unique(all(cmp)) - cmp.begin());
    for(int i =1 ;i <= n;i++) arr[i] = lower_bound(all(cmp),arr[i]) - cmp.begin() + 1;
    dfs(1);
    HLD(1,1);
    
    stk[1].pb({arr[1],1});
    for(auto [a,b] : E){
        cout << ask(a) << endl;
        update(b,arr[b]);
    }
    return 0;
}

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