Submission #915160

#	Time	Username	Problem	Language	Result	Execution time	Memory
915160		ThylOne	Two Currencies (JOI23_currencies)	C++14	0 / 100	492 ms	183492 KiB

currencies

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

    #define int long long
    using ll = long long;
    using namespace std;
    const int maxiN = 1000000;
    const int LOG = 18;
    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];
    }
    map < int, vector < int >> peages;
    vector < int > val[maxiN];

    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;
    }
    struct segtree{
        vector<int> vals;
        int leaf;
        segtree(int n){
            leaf = (1<<((int)ceil(log2(n))));
            vals.resize(2*leaf);
            fill(vals.begin(),vals.end(),0);
        }
        void _addRange(int a,int b,int 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,int val){
            _addRange(a+leaf,b+leaf,val);
        }
        int getVal(int pos){
            pos+=leaf;
            int re = 0;
            for(int p=pos;p>=1;p>>=1){
                re+=vals[p];
            }
            return re;
        }
    };
    signed main() {
        
        
        
        fill(depth, depth + maxiN, -1);
        int n, m, q;
        cin >> n >> m >> q;
        segtree counter(3*n);
        vector < pair < int, int >> edges;
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            edges.push_back(make_pair(a, b));
            links[a].push_back(b);
            links[b].push_back(a);
        }
        root(0, 0, -1);
        int C=-1;
        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);
            peages[c].push_back(a);
            val[a].push_back(c);
        }
        //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];
            }
        }
        computeEuleurTour(0);
        for(int i = 0;i<n;i++){
            counter.addRange(eulerseg[i].first,eulerseg[i].second,val[i].size());
        }
        for (int i = 0; i < q; i++) {
            int a, b, x, y;
            cin >> a >> b >> x >> y;
            a--;
            b--;
            int lca = LCA(a, b);
            int nbocc = counter.getVal(eulerseg[a].first) + counter.getVal(eulerseg[b].first) - 2*counter.getVal(eulerseg[lca].first);
            if(C==-1)return -42;
            int nb_silver = y/C;
            int g=0;
            if(nb_silver>=nbocc){g=0;}
            else{g=nbocc-nb_silver;}
            if(g<=x){
                cout<<x-g<<endl;
            }else{
                cout<<-1<<endl;
            } 
        }
        return 0;
        
};

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