Submission #93640

#	Time	Username	Problem	Language	Result	Execution time	Memory
93640		samzhang	Construction of Highway (JOI18_construction)	C++14	100 / 100	817 ms	23836 KiB

construction

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize(3)
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("sse3","sse2","sse")
//#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
//#pragma GCC target("f16c")
//#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
//#pragma GCC diagnostic error "-fwhole-program"
//#pragma GCC diagnostic error "-fcse-skip-blocks"
//#pragma GCC diagnostic error "-funsafe-loop-optimizations"
//#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define sz(x) ((int)x.size())
#define EX0 exit(0);

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
    if(a<0)return -1;
    if(a>0)return 1;
    return 0;
}
string to_string(string s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) {}
#endif

template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}

template<typename T> inline void in(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch))  {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}

ll twop(int x) {
    return 1LL<<x;
}

template<typename A,typename B > inline void in(A&x,B&y) {
    in(x);
    in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
    in(x);
    in(y);
    in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
    in(x);
    in(y);
    in(z);
    in(d);
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
namespace SOLVE {
    
    int color[100010];
    int relabel[100010];
    struct SegTree{
        static const int maxn = 100010;
        
        struct node{
            int l,r;
            int cover;
        };
        
        node no[maxn*4];
        void push_up(int ind){
            
        }
        void push_down(int ind){
            if(no[ind].cover >= 1){
                no[lson].cover = no[rson].cover = no[ind].cover;
                no[ind].cover = 0;
            }
        }
        void build(int l,int r,int ind){
            no[ind].l = l;
            no[ind].r = r;
            if(l == r){
                (no[ind].cover = relabel[l]);
            }else{
                int mid = (l+r)/2;
                build(l,mid,lson);
                build(mid+1,r,rson);
                push_up(ind);
            }
        }
        void update(int l,int r,int ind,int val){
            if(l>no[ind].r || r<no[ind].l)return;
            if(l<=no[ind].l && no[ind].r <= r){
                no[ind].cover = val;
            }else{
                push_down(ind);
                update(l,r,lson,val);
                update(l,r,rson,val);
                push_up(ind);
            }
        }
        void query(int l,int r,int ind,vector<PII>& ans){
            if(l>no[ind].r || r<no[ind].l)return;
            if(no[ind].cover){
                ans.PB(MP(min(r,no[ind].r) - max(l,no[ind].l)+1,no[ind].cover));
            }else{
                push_down(ind);
                query(l,r,lson,ans);
                query(l,r,rson,ans);
                push_up(ind);
            }
        }
    };
    
    
    SegTree tree;

    namespace HLD {
        //0不能被使用
        struct edge {
            int to;
            edge(int x):to(x){}
        };
        
        const int root = 1;
        const int maxn = 100010;
        vector<edge>adj[maxn];
        int dfnToID[maxn],dfn[maxn],head[maxn],fa[maxn],dep[maxn],size[maxn],heavy[maxn],r[maxn],cnt = 1;
        void firstDfs(int cur,int _fa) {
            dep[cur] = dep[_fa]+1;
            size[cur]=1;
            fa[cur] = _fa;
            for(auto e:adj[cur]) {
                if(e.to!=_fa) {
                    firstDfs(e.to,cur);
                    size[cur]+=size[e.to];
                }
            }
            int heavyChild = 0;
            for(auto e:adj[cur]) {
                if(e.to!=_fa) {
                    if(size[e.to]>size[heavyChild]) {
                        heavyChild = e.to;
                    }
                }
            }
            heavy[cur] = heavyChild;
        }
        
        
        void secondDfs(int cur,int _fa) {
            if(cur!=heavy[_fa]) {
                head[cur] = cur;
            } else {
                head[cur] = head[_fa];
            }
            dfn[cur] = cnt++;
            r[cur] = dfn[cur];
            dfnToID[dfn[cur]] = cur;
            if(!heavy[cur])return;
            secondDfs(heavy[cur],cur);
            r[cur] = r[heavy[cur]];
            for(auto e:adj[cur]) {
                if(e.to==_fa||e.to==heavy[cur])continue;
                secondDfs(e.to,cur);
                r[cur] = r[e.to];
            }
        }
        void init() {
            firstDfs(root,0);
            secondDfs(root,0);
        }
        
        int kthFather(int k,int cur) {
            while(k) {
                if(head[cur] == cur) {
                    k--;
                    cur = fa[head[cur]];
                } else {
                    if(dep[cur]-dep[head[cur]]<=k) {
                        k-=dep[cur]-dep[head[cur]];
                        cur = head[cur];
                    } else {
                        return dfnToID[dfn[cur]-k];
                    }
                }
            }
            return cur;
        }
        int LCA(int u,int v) {
            while(head[u]!=head[v]) {
                if(dep[head[u]]>dep[head[v]])swap(u,v);
                v = fa[head[v]];
            }
            if(dep[u]<dep[v])return u;
            return v;
        }
        
        int dis(int u,int v){
            return dep[u]+dep[v]-2*dep[LCA(u, v)];
        }
        void getColors(int u,vector<PII>&ans){
            if(u == 0)return;
            getColors(fa[head[u]], ans);
            tree.query(dfn[head[u]], dfn[u], 1, ans);
        }
        bool cmp(PII a,PII b){
            return a.se>b.se;
        }
        
        ll gao(vector<PII>::iterator s,vector<PII>::iterator t){
            if(t == s+1)return 0;
            auto mid = s + (t-s)/2;
            ll ans = gao(s, mid) + gao(mid, t);
            ll cnt = 0;
            auto cur = s;
            for(auto i = mid;i!=t;i++){
                while(cur!=mid and cur->se > i->se){
                    cnt += cur->fi;
                    ++cur;
                }
                ans += cnt * i->fi;
            }
            inplace_merge(s, mid, t,cmp);
            
            
            
            
            
            
            return ans;
        }
        
        void solve(int u){
            vector<PII>ans;
            getColors(u, ans);
            int last_color = ans.back().se;
            ans.pop_back();
            cout<<gao(begin(ans), end(ans))<<endl;
            while(u!=0){
                tree.update(dfn[head[u]], dfn[u],1,last_color);
                u = fa[head[u]];
            }
        }
        
    }
    vector<PII>pr;
    void main(){
        int n;in(n);
        REP(i,1,n+1)in(color[i]);
        REP(i,1,n){
            int a,b;in(a,b);
            HLD::adj[a].PB(b);
            pr.PB(MP(a,b));
        }
        HLD::init();
        REP(i,1,n+1){
            relabel[HLD::dfn[i]] = color[i];
        }
        tree.build(1, n, 1);
        for(auto i:pr){
            HLD::solve(i.se);
        }
        
        
        
        
        
        
        
        
        
        
    }
}


signed main() {
    
    
    
    
    
    int t;
//    in(t);
    t = 1;
    while(t--){
        SOLVE::main();
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

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