Submission #915849

#	Time	Username	Problem	Language	Result	Execution time	Memory
915849		ThylOne	Two Currencies (JOI23_currencies)	C++14	0 / 100	216 ms	30552 KiB

currencies

//####################
//TwoCurrencies
//####################
#include<bits/stdc++.h>
    

using ll = long long;
using namespace std;
const int maxiN = 1000042;
const int LOG = 18;
    
int n, m, q;
vector < int > links[maxiN];
int depth[maxiN];
int up[maxiN][LOG];
void root(int node, int d = 0, int parent = -1) {
    up[node][0] = parent;
    depth[node] = d;
    for (int v: links[node])
        if (v != parent) {
            root(v, d + 1, node);
        }
}
int getK(int node, int K) {
    for (int i = LOG - 1; i >= 0; i--) {
        if ((K >> i) & 1) {
            node = up[node][i];
        }
    }
    return node;
}
int LCA(int a, int b) {
    if (depth[b] > depth[a]) swap(a, b);
    a = getK(a, depth[a] - depth[b]);
    if (a == b) {
        return a;
    }
    for (int l = LOG - 1; l >= 0; l--) {
        if (up[a][l] != up[b][l]) {
            a = up[a][l];
            b = up[b][l];
        }
    }
    return up[a][0];
}
    
pair<int,int> eulerseg[maxiN];
int actEuleur=-1;
void computeEuleurTour(int node,int parent = -1){
    actEuleur++;
    eulerseg[node].first = actEuleur;
    for(int v:links[node])if(parent!=v){
        computeEuleurTour(v,node);
    }
    actEuleur++;
    eulerseg[node].second = actEuleur;
}
template<typename T>
struct segtree{
    vector<T> vals;
    int leaf;
    segtree(int n){
        leaf = (1<<((int)ceil(log2(n))));
        vals.resize(2*leaf);
        fill(vals.begin(),vals.end(),0);
    }
    segtree()=default;
    void init(int n){
        leaf = (1<<((int)ceil(log2(n))));
        vals.resize(2*leaf);
        fill(vals.begin(),vals.end(),0);
    }
    void reset(){
        fill(vals.begin(),vals.end(),0);
    }
    void _addRange(int a,int b,T val){
        if(a==b){
            vals[a]+=val;
        }else if(a&1){
            vals[a]+=val;
            _addRange(a+1,b,val);
        }else if(b%2==0){
            vals[b]+=val;
            _addRange(a,b-1,val);
        }else{
            _addRange(a/2,b/2,val);
        }
    }
    void addRange(int a,int b,T val){
        _addRange(a+leaf,b+leaf,val);
    }
    T getVal(int pos){
        pos+=leaf;
        int re = 0;
        for(int p=pos;p>=1;p>>=1){
            re+=vals[p];
        }
        return re;
    }
};
    
struct req{
    int a,b;
    ll x,y;
    int lca;
    ll totalSum;
};
vector<pair<ll,int>> W_child;
vector<req> queries;
vector<pair<ll,int>> ans;
struct node{
    int deb,fin;
    vector<int> id_req;
};
int middle(node&node_){
    int m = (node_.deb+node_.fin)/2;
    if(m==node_.fin)m=node_.deb;
    return m;
}
segtree<ll> pathsum;
segtree<int> occurence;
pair<ll,int> computePath(int a,int b,int lca){
    ll nbocc=0;
    ll sumGold=0;
    if(a==lca && b==lca){
        nbocc=0;
    }else if(a==lca){
        nbocc=occurence.getVal(eulerseg[b].first)-occurence.getVal(eulerseg[a].first);
        sumGold=pathsum.getVal(eulerseg[b].first)-  pathsum.getVal(eulerseg[a].first);
    }else if(b==lca){
        nbocc=occurence.getVal(eulerseg[a].first)-occurence.getVal(eulerseg[b].first);
        sumGold=pathsum.getVal(eulerseg[a].first)-  pathsum.getVal(eulerseg[b].first);
    }else{
        nbocc=occurence.getVal(eulerseg[b].first)+occurence.getVal(eulerseg[a].first)-2*occurence.getVal(eulerseg[lca].first);;
        sumGold=pathsum.getVal(eulerseg[b].first)+  pathsum.getVal(eulerseg[a].first)-  2*pathsum.getVal(eulerseg[lca].first);;
    }
    return {sumGold,nbocc};
}
vector<bool> oracle(vector<int> reqs,int p){
    vector<bool> bans(reqs.size());
    for(int i=0;i<reqs.size();i++){
        pair<ll,int> rep = computePath(queries[reqs[i]].a,queries[reqs[i]].b,queries[reqs[i]].lca);
        if(queries[reqs[i]].x>=rep.second && queries[reqs[i]].y>=(queries[reqs[i]].totalSum-rep.first)){
            bans[i]=true;
        }else{
            bans[i]=false;
        }
    }
    return bans;
}
void parallel_binary_search(){
    //usagé donc on nettoie
    pathsum.reset();
    occurence.reset();
    
    vector<int> ids;
    for(int i = 0;i<q;i++){
        ids.push_back(i);
    }
    node first = {0,m,ids};
    vector<node> nodes = {first};
    
    for(int lvl=0;lvl<LOG;lvl++){
        pathsum.reset();
        occurence.reset();
        int actPush = m;
        vector<node> next_lvl;
        
        if(nodes.size()){
            for(node &node_:nodes){
                if(node_.id_req.empty())continue;
                int mid = middle(node_);
                if(mid>actPush){
                    cerr<<"error !"<<endl;
                }
                while(actPush>mid){
                    actPush--;
                    pathsum.addRange(eulerseg[W_child[actPush].second].first,eulerseg[W_child[actPush].second].second,W_child[actPush].first);
                    occurence.addRange(eulerseg[W_child[actPush].second].first,eulerseg[W_child[actPush].second].second,1);
                }
                
                vector<bool> dir = oracle(node_.id_req,mid);
                node left,right;
                left.deb = node_.deb;
                left.fin = mid;
                right.deb = mid+1;
                right.fin = node_.fin;
    
                for(int i = 0;i<node_.id_req.size();i++){
                    if(dir[i]){
                        if(node_.deb!=node_.fin){
                            right.id_req.push_back(node_.id_req[i]);
                        }
                        ans[node_.id_req[i]] = computePath(queries[node_.id_req[i]].a,queries[node_.id_req[i]].b,queries[node_.id_req[i]].lca);
                    }else{
                        if(node_.deb!=node_.fin){
                            left.id_req.push_back(node_.id_req[i]);
                        }
                    }
                }
                    
                    next_lvl.push_back(right);
                    next_lvl.push_back(left);
                
            }            
            swap(nodes,next_lvl);
        }else{
            break;
        }
    }
}
signed main() {
    
    fill(depth, depth + maxiN, -1);
    
    cin >> n >> m >> q;
    queries.resize(q);
    occurence.init(2*n);
    pathsum.init(2*n);
    ans.resize(q);
    for(int i = 0;i<q;i++)ans[i] = {-1,-1};
    vector < pair < int, int >> edges;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edges.push_back({a,b});
        links[a].push_back(b);
        links[b].push_back(a);
    }
    root(0, 0, -1);
    int C=-1;
    computeEuleurTour(0);
    
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c;
        C = c;
        p--;
        auto a = edges[p].first;
        auto b = edges[p].second;
        if (depth[a] < depth[b]) swap(a, b);  
        occurence.addRange(eulerseg[a].first,eulerseg[a].second,1);
        pathsum.addRange(eulerseg[a].first,eulerseg[a].second,C);
        W_child.push_back({c,a});
    }
    sort(W_child.begin(),W_child.end());
    //On calcule la tab de LCA
    for (int l = 1; l < LOG; l++) {
        for (int i = 0; i < n; i++) {
            if (up[i][l - 1] == -1) {
                up[i][l] = -1;
            }
            up[i][l] = up[up[i][l - 1]][l - 1];
        }
    }
    
    
    for (int i = 0; i < q; i++) {
        int a,b;
        ll x, y;
        cin >> a >> b >> x >> y;
        a--;
        b--;
        int lca = LCA(a, b);
        queries[i] = {a,b,x,y,lca,computePath(a,b,lca).first};
    }
    pathsum.reset();
    occurence.reset();
    vector<int> req;for(int i = 0;i<q;i++)req.push_back(i);
    for(int borne = m;borne>=0;borne--){
        if(borne!=m){
            pathsum.addRange(eulerseg[W_child[borne].second].first,eulerseg[W_child[borne].second].second,W_child[borne].first);
            occurence.addRange(eulerseg[W_child[borne].second].first,eulerseg[W_child[borne].second].second,1);
        }

        vector<bool> dir = oracle(req,borne);
        for(int i = 0;i<q;i++){
            if(dir[i] && ans[i].first==-1 && ans[i].second==-1){
                ans[i] = computePath(queries[i].a,queries[i].b,queries[i].lca);
            }
        }
    }
    //parallel_binary_search();
    
    for(int i = 0;i<q;i++){
        ll tot = queries[i].totalSum-ans[i].first;
        if(ans[i].first==-1 && ans[i].second==-1){
            cout<<-1<<'\n';
            continue;
        }
        if(queries[i].x>=ans[i].second && queries[i].y>=tot){
            cout<<queries[i].x-ans[i].second<<'\n';
        }else{
            cout<<-1<<'\n';;
        }
    }
    return 0;
    
};

Compilation message (stderr)

currencies.cpp: In function 'std::vector<bool> oracle(std::vector<int>, int)':
currencies.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for(int i=0;i<reqs.size();i++){
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void parallel_binary_search()':
currencies.cpp:189:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |                 for(int i = 0;i<node_.id_req.size();i++){
      |                               ~^~~~~~~~~~~~~~~~~~~~

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