Submission #925216

#	Time	Username	Problem	Language	Result	Execution time	Memory
925216		HuyAT	Two Currencies (JOI23_currencies)	C++14	0 / 100	4 ms	9052 KiB

currencies

#include<bits/stdc++.h>

const int MaxN = 1e5 + 10;
const int MaxBit = 20;

int n,m,k,timeIn[MaxN + 1],timeOut[MaxN + 1],parent[MaxN + 1][MaxBit + 1],timer = 0;
std::vector<int> adj[MaxN + 1];

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

    }
    void update(int idx,long long val){
        for(int i = idx;i < (int)bit.size();i += (i & (-i))){
            bit[i] += val;
        }
    }
    void updateRange(int l,int r,long long val){
//        if(!(r >= 1 && r <= n)){
//            r = r;
//            assert(false);
//        }
//        assert(l >= 1 && l <= n);
//        assert(r >= 1 && r <= n);
        update(l,val);
        update(r + 1,-val);
    }
    long long getSum(int idx){
        long long ans =0 ;
        for(int i = idx;i > 0;i -= (i & (-i))){
            ans += bit[i];
        }
        return ans;
    }
};
struct Query{
    int gold,silver,u,v,lo,hi,mid,ans,index;
    Query() :gold(0),silver(0),u(0),v(0),lo(0),hi(0),mid(0),ans(0),index(0){

    }
    bool operator < (const Query &other){
        return (mid < other.mid);
    }
}query[MaxN + 1];
struct Edge{
    int u,v,w;
    bool operator < (const Edge &other){
        return (w < other.w);
    }
};
std::vector<Edge> edge;

void readData(){
    std::cin >> n >> m >> k;
    edge.push_back({0,0,0});
    for(int i = 1;i < n;++i){
        int a,b;
        std::cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge.push_back({a,b,0});
    }
    for(int i = 1;i <= m;++i){
        int p,c;
        std::cin >> p >> c;
        edge.push_back({edge[p].u,edge[p].v,c});
    }
    std::sort(edge.begin(),edge.end());
    for(int i = 1;i <= k;++i){
        std::cin >> query[i].u >> query[i].v >> query[i].gold >> query[i].silver;
        query[i].index = i;
        query[i].lo = n - 1,query[i].hi = (int)edge.size() - 1;
        query[i].mid = (query[i].lo + query[i].hi) / 2;
    }
}
void dfs(int u = 1,int par = 1){
    timeIn[u] = ++timer;
    parent[u][0] = par;
    for(int v : adj[u]){
        if(v == par){
            continue;
        }
        dfs(v,u);
    }
    timeOut[u] = timer;
}
void binaryLift(){
    for(int i = 1;i <= MaxBit;++i){
        for(int j = 1;j <= n;++j){
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }
    }
}
bool isAncestor(int u,int v){
    return (timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v]) ;
}
int lca(int u,int v){
    if(isAncestor(u,v)){
        return u;
    }
    if(isAncestor(v,u)){
        return v;
    }
    for(int i = MaxBit;i >= 0;--i){
        if(!isAncestor(parent[u][i],v)){
             u = parent[u][i];
        }
    }
    return parent[u][0];
}

void parallelBinarySearch(){
    for(Edge &e : edge){
        if(!isAncestor(e.u,e.v)){
            std::swap(e.u,e.v);
        }
    }
    for(int i = 1;i <= 20;++i){
        int it = n - 1;
        FenwickTree ft(n);
        std::sort(query + 1,query + k + 1);
        std::function<long long(int,int)> getSum = [&](int u,int v){
            int l = lca(u,v);
            return ft.getSum(timeIn[u]) + ft.getSum(timeIn[v]) - ft.getSum(timeIn[l]) * 2LL;
        };
        for(int j = 1;j <= k;++j){
            if(query[j].lo > query[j].hi){
                continue;
            }
            while(it < query[j].mid){
                ++it;
//                if(it > m && it < (int)edge.size()){
//                    it = it;
//                }
//                assert(it > m && it < (int)edge.size());
//                std::cerr << edge[it].v << "\n";
                ft.updateRange(timeIn[edge[it].v],timeOut[edge[it].v],edge[it].w);
            }
            long long s = getSum(query[j].u,query[j].v);
//            if(s > 16){
//                std::cerr << s << "\n";
//            }
            if(s <= query[j].silver){
                query[j].ans = query[j].mid;
                query[j].lo = query[j].mid + 1;
            }else{
                query[j].hi = query[j].mid - 1;
            }
            query[j].mid = (query[j].lo + query[j].hi) / 2;
        }
    }
}
void answer(){
    std::vector<int> ans(k + 1);
    std::sort(query + 1,query + k + 1,[](const Query &a,const Query &b){
        return a.ans < b.ans;
    });
    int it = (int)edge.size();
    FenwickTree ft(n);
    for(int i = k;i >= 1;--i){
        std::function<long long(int,int)>getSum = [&](int u,int v){
            int l = lca(u,v);
            return ft.getSum(timeIn[u]) + ft.getSum(timeIn[v]) - ft.getSum(timeIn[l]) * 2LL;
        };
//        std::cerr << query[i].ans << "\n";
        while(it > query[i].ans + 1){
            --it;
//            std::cerr << edge[it].v << "\n";
            ft.updateRange(timeIn[edge[it].v],timeOut[edge[it].v],1);
        }
        long long s = getSum(query[i].u,query[i].v);
        if(s > query[i].gold){
            ans[query[i].index] = -1;
        }else{
            ans[query[i].index] = query[i].gold - s;
        }
    }
    for(int i = 1;i <= k;++i){
        std::cout << ans[i] << "\n";
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    dfs();
    binaryLift();
    parallelBinarySearch();
    answer();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32