Submission #797887

#	Time	Username	Problem	Language	Result	Execution time	Memory
797887		vjudge1	Construction of Highway (JOI18_construction)	C++17	16 / 100	2071 ms	12548 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace std;
using namespace __gnu_pbds;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>st;

const int N = 1e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N] , sz[N] = {} , h[N] = {} , us[N]  , p[N] , cnt = 0;

vector<int>v[N];

/*
void get_sz(int n , int p= 0){
    sz[n] = 1;
    for(auto to : v[n])
        if(to != p){
            get_sz(to , n);
    if(sz[to] > h[n] && n)
        h[n] = sz[to] , swap(v[n][0] ,to);
    }
    sz[p] += sz[n];
}*/
void dfs(int n){
    for(auto to : v[n])
        if(p[n] != to)
            p[to] = n , dfs(to);
}

void solve(){
    ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
    cin>>n;
    for(i = 1; i <= n; i++)
        cin>>a[i]  , d[i] = a[i];
    for(i = 1; i < n; i++){
        cin>>b[i]>>c[i];
        v[b[i]].pb(c[i]);
        v[c[i]].pb(b[i]);
    }
    dfs(1);
    for(i = 1; i < n; i++){
        l = b[i] , r = c[i];
        cnt= s =  0;
        while(l){
            if(st.size() && st.begin()->fi < d[l]){
            auto it = st.lower_bound({d[l] , 0});
            it--;
            x = st.order_of_key({it->fi , it->se});
            s += x + 1;
            }
            st.insert({d[l],++cnt});
            l = p[l];
        }
        cout<<s<<"\n";
        l = b[i];
        while(l)
            d[l] = a[c[i]] , l =  p[l];
        st.clear();

    }
}

int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

construction.cpp: In function 'void solve()':
construction.cpp:51:8: warning: unused variable 'q' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |        ^
construction.cpp:51:16: warning: unused variable 'j' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                ^
construction.cpp:51:20: warning: unused variable 'm' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                    ^
construction.cpp:51:26: warning: unused variable 'z' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                          ^
construction.cpp:51:38: warning: unused variable 'f' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                      ^
construction.cpp:51:45: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                             ^
construction.cpp:51:49: warning: unused variable 'k' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                 ^
construction.cpp:51:57: warning: unused variable 'y' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                         ^
construction.cpp:51:61: warning: unused variable 'mn' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                             ^~
construction.cpp:51:74: warning: unused variable 'mx' [-Wunused-variable]
   51 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                                          ^~

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