Submission #482011

#	Time	Username	Problem	Language	Result	Execution time	Memory
482011		leaked	Construction of Highway (JOI18_construction)	C++14	16 / 100	1899 ms	37572 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <class T> using oset=tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N=1e5+3;
struct segtree{
    pii t[4*N];
    segtree(){
        fill(t,t+4*N,m_p(-2e9,1));
    }
    void upd(int id,pii x,int v=1,int tl=0,int tr=N-1){
        if(tl==tr){
            umax(t[v],x);
//            debug()<<imie(t[v])imie(x);
            return;
        }
        int tm=(tl+tr)>>1;
        if(tm>=id)
            upd(id,x,2*v,tl,tm);
        else
            upd(id,x,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    pii get(int l,int r,int v=1,int tl=0,int tr=N-1){
        if(tl>=l&&tr<=r) return t[v];
        if(tl>r||tr<l) return {-2e9,1};
        int tm=(tl+tr)>>1;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}seg;
struct fenwick{
    int fnw[N];
    fenwick(){
        fill(fnw,fnw+N,0);
    }
    vec<pii>up;
    void upd(int i,int x,bool t=1){
        if(t) up.pb({i,-x});
        while(i<N){
            fnw[i]+=x;
            i+=i&-i;
        }
    }
    int get(int i){
        int ans=0;
        while(i>0){
            ans+=fnw[i];
            i-=i&-i;
        }
        return ans;
    }
    int get(int l,int r){
        return get(r)-get(l-1);
    }
    void clr(){
//        debug()<<imie(up);
        for(auto &z : up)
            upd(z.f,z.s,0);
        up.clear();
    }
}fnw;
vec<int> g[N];
int up[N][20],tin[N],tout[N],tt=1;
void dfs(int v,int p){
    up[v][0]=p;
    tin[v]=tt++;
//    debug()<<imie()
    for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs(z,v);
    }
    tout[v]=tt-1;
//    debug()<<imie(v)imie(tin[v])imie(tout[v]);
}
signed main(){
    fast_ioi;
//    return 0;
    int n;
    cin>>n;
    vec<int>a(n);
    for(auto &z : a) cin>>z;
    vec<int> kek=a;
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    for(auto &z : a) z=lower_bound(all(kek),z)-kek.begin()+1;
    vec<pii>e;
    for(int i=1;i<n;i++){
        int v, u;
        cin >> v >> u;//--v; --u;
        e.pb({v,u});
        g[v].pb(u);
    }
    g[0].pb(1);
    dfs(0,0);
    seg.upd(tin[1],{-1,a[0]});
//    return 0;
    int sm=0;
    for(int i=0;i<n-1;i++){
        ll ans=0;
        int v=e[i].f;
        vec<pii>arr;
        while(v){
            /// find max u
            int cnt=0;
            for(int j=19;j>=0;j--){
                if(up[v][j]!=0
                   &&
                   seg.get(tin[up[v][j]],tout[up[v][j]])==seg.get(tin[v],tout[v]))
                    v=up[v][j],cnt+=(1<<j);
            }
            arr.pb({seg.get(tin[v],tout[v]).s,cnt+1});
            if(v!=1)
                assert(seg.get(tin[v],tout[v])!=seg.get(tin[up[v][0]],tout[up[v][0]]));
            v=up[v][0];
        }
        sm+=sz(arr);
        assert(sm<=10*n);
//        debug()<<imie(arr);
        for(auto &z : arr){
            ans+=1ll*z.s*fnw.get(z.f-1);
            fnw.upd(z.f,z.s);
        }
        fnw.clr();
        cout<<ans<<'\n';
        seg.upd(tin[e[i].s],{i,a[e[i].s-1]});
//        if(i==1) return 0;
//        for(int i=0;i<=n;i++)
//            debug()<<imie(i)imie(seg.get(tin[i],tout[i]));
//        debug()<<imie(*max_element(fnw.fnw,fnw.fnw+N));
//        debug()<<imie()
    }
    return 0;
}
/*
5
4
0
0
0
1
2
3
0
*/

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