Submission #481998

#	Time	Username	Problem	Language	Result	Execution time	Memory
481998		leaked	Construction of Highway (JOI18_construction)	C++14	0 / 100	3 ms	6092 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<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]});
        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});
                v=up[v][0];
            }
    //        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]});
    //        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: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84