Submission #1283715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283715		HuyAT	Construction of Highway (JOI18_construction)	C++20	100 / 100	519 ms	22372 KiB

construction

#include<bits/stdc++.h>
#define newl '\n'

const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;


struct FenwickTree{
    std::vector<int> bit;
    FenwickTree(int n) : bit(n + 1,0){

    }
    void update(int idx,int v){
        for(int i = idx;i < (int)bit.size();i += (i & (-i))){
            bit[i] += v;
        }
    }
    int sum(int idx){
        int ans = 0;
        for(int i = idx;i > 0;i -= (i & (-i))){
            ans += bit[i];
        }
        return ans;
    }
};
struct Node{
    int min_val,max_val,lazy;
    Node() : min_val(0),max_val(0),lazy(-1){

    }
    Node operator + (const Node &other) const {
        Node res;
        res.min_val = std::min(min_val,other.min_val);
        res.max_val = std::max(max_val,other.max_val);
        res.lazy = -1;
        return res;
    }
};
struct SegmentTree{
    int n;
    std::vector<Node> st;
    SegmentTree(int n) : n(n),st(n * 4 + 10,Node()){

    }
private:
    void down(int id){
        if(st[id].lazy != -1){
            st[id << 1].min_val = st[id << 1].max_val = st[id << 1].lazy = st[id].lazy;
            st[id << 1 | 1].min_val = st[id << 1 | 1].max_val = st[id << 1 | 1].lazy = st[id].lazy;
            st[id].lazy = -1;
        }
    }
    void update(int l,int r,int u,int v,long long val,int id = 1){
        if(u <= l && r <= v){
            st[id].min_val = st[id].max_val = st[id].lazy = val;
            return;
        }
        down(id);
        int mid = (l + r) / 2;
        if(v <= mid){
            update(l,mid,u,v,val,id << 1);
        }else if(u > mid){
            update(mid + 1,r,u,v,val,id << 1 | 1);
        }else{
            update(l,mid,u,v,val,id << 1);
            update(mid + 1,r,u,v,val,id << 1 | 1);
        }
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    Node query(int l,int r,int u,int v,int id = 1){
        if(u <= l && r <= v){
//            assert(st[id].max_val != -1);
            return st[id];
        }
        down(id);
        int mid = (l + r) / 2;
        if(v <= mid){
            return query(l,mid,u,v,id << 1);
        }
        if(u > mid){
            return query(mid + 1,r,u,v,id << 1 | 1);
        }
        return query(l,mid,u,v,id << 1) + query(mid + 1,r,u,v,id << 1 | 1);

    }
    int walk(int l,int r,int pos,int v,int id = 1){
        if((st[id].min_val == v && st[id].max_val == v) || l > pos){
            return -1;
        }
        if(l == r){
//            std::cout << "IMP " << st[id].min_val << " " << st[id].max_val << newl;
//            exit(0);
            return l;
        }
        down(id);
        int mid = (l + r) / 2;
        int ans = walk(mid + 1,r,pos,v,id << 1 | 1);
        if(ans != -1){
            return ans;
        }
        return walk(l,mid,pos,v,id << 1);
    }
public:
    void update(int l,int r,long long w){
        update(1,n,l,r,w);
    }
    Node query(int l,int r){
        if(l > r){
            return Node();
        }
        return query(1,n,l,r);
    }
    int walk(int pos,int v){
        return walk(1,n,pos,v);
    }
};
struct Solver{
    int n,timer;
    std::vector<std::vector<int>> adj;
    std::vector<int> c,order,f,par,tp,in,ver;
    Solver() : timer(0){

    }
    void readData(){
        std::cin >> n;
        adj.resize(n + 1);
        c.assign(n + 1,0);
        order.assign(n + 1,0);
        f.assign(n + 1,0);
        par.assign(n + 1,0);
        tp.assign(n + 1,0);
        in.assign(n + 1,0);
        ver.assign(n + 1,0);
        for(int i = 1;i <= n;++i){
            std::cin >> c[i];
        }
        for(int i = 2;i <= n;++i){
            int u,v;
            std::cin >> u >> v;
            adj[u].emplace_back(v);
            order[i] = v;
        }
    }
    void prepare(){
        std::set<int> s(c.begin() + 1,c.end());
        std::vector<int> v(s.begin(),s.end());
        for(int i = 1;i <= n;++i){
            c[i] = std::upper_bound(v.begin(),v.end(),c[i]) - v.begin();
        }
    }
    void get_size(int u = 1){
        f[u] = 1;
        for(int &v : adj[u]){
            par[v] = u;
            get_size(v);
            f[u] += f[v];
            if(f[v] > f[adj[u][0]]){
                std::swap(v,adj[u][0]);
            }
        }
    }
    void dfs(int u = 1){
        in[u] = ++timer;
        ver[timer] = u;
        for(int v : adj[u]){
            tp[v] = (v == adj[u][0] ? tp[u] : v);
            dfs(v);
        }
    }
    void solve(){
        SegmentTree T(n);
        FenwickTree bit(n);
        T.update(1,1,c[1]);
        std::vector<std::pair<int,int>> v;
        auto prepare = [&](int u){
            u = par[u];
            while(u != 0){
//                std::cerr << u << newl;
                int cur = T.query(in[u],in[u]).max_val;
                int it = T.walk(in[u],cur);
                if(it < in[tp[u]]){
                    v.emplace_back(cur,in[u] - in[tp[u]] + 1);
                    u = par[tp[u]];
                }else{
                    v.emplace_back(cur,in[u] - it);
                    u = ver[it];
                }
            }
        };
        auto cnt_contribute = [&](int u) -> long long{
            prepare(u);
            long long ans = 0;
//            std::reverse(v.begin(),v.end());
            for(std::pair<int,int> cur : v){
//                if(u == 5){
//                    std::cout << cur.first << " " << cur.second << newl;
//                }
                ans += bit.sum(cur.first - 1) * (long long)cur.second;
                bit.update(cur.first,cur.second);
            }
            for(std::pair<int,int> cur : v){
                bit.update(cur.first,-cur.second);
            }
            v.clear();
            return ans;
        };
        auto update = [&](int u){
            int v = c[u];
            while(u != 0){
                T.update(in[tp[u]],in[u],v);
                u = par[tp[u]];
            }
        };
        for(int i = 2;i <= n;++i){
            std::cout << cnt_contribute(order[i]) << newl;
            update(order[i]);
        }
    }
    void main(){
        readData();
        prepare();
        get_size();
        tp[1] = 1;
        dfs();
        solve();
    }
};
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    Solver().main();
    return 0;
}
/*
5
12923 10000 230 9012 100000
1 2
2 3
2 4
3 5
*/

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