Submission #1262292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262292		SzymonKrzywda	Two Currencies (JOI23_currencies)	C++20	0 / 100	24 ms	5540 KiB

currencies

#include <bits/stdc++.h>


using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;

#define ff first
#define ss second
#define int long long


const int MAXN = 1e5 + 7;

struct LCA{
    int n, LOG, aktpre;
    vector<vi> graf;
    vector<vi> jump;
    vi preorder;
    vi depth;
    vi max_pre;

    void init(int N, vector<vi> kopia_graf) {
        graf = kopia_graf;
        n = N;
        LOG = ceil(log2(n)) + 1;
        jump.assign(n, vi(LOG, 0));
        depth.assign(n, 0);
        preorder.assign(n, 0);
        max_pre.assign(n, 0);
        aktpre = 0;
        dfs(0, 0);
        preprocess();
    }

    

    void dfs(int v, int p) {
        preorder[v] = aktpre++;
        max_pre[v] = preorder[v];
        jump[v][0] = p;
        for (int s : graf[v]) {
            if (p != s) {
                depth[s] = depth[v] + 1;
                dfs(s, v);
                max_pre[v] = max(max_pre[v], max_pre[s]);
            }
        }
    } 

    void preprocess() {
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                jump[v][k] = jump[jump[v][k - 1]][k - 1];
            }
        }
    }

    int lca(int a, int b) {
        ////cout << "Szukam LCA: " << a << ' ' << b << '\n';
        if (a == b) return a;
        if (depth[a] < depth[b]) swap(a, b);

        for (int k = LOG - 1; k >= 0; k--) {
            if (depth[a] - (1 << k) >= depth[b]) a = jump[a][k];
        }
        //////cout << "O koniec 1\n";

        if (a == b) return a;

        for (int k = LOG - 1; k >= 0; k--) {
            if (jump[a][k] != jump[b][k]) {
                a = jump[a][k];
                b = jump[b][k];
            }
        }
       // ////cout << "O koniec 2\n";

        return jump[a][0];
    }
};

const int base = 1 << 17;
vector<int> tree;
vector<int> tree2;

void add(int l, int r, int val = 1) {
    l += base - 1;
    r += base + 1;

    while (l / 2 != r / 2) {
        if (l % 2 == 0) {
            tree[l + 1] += val;
            tree2[l + 1] ++;
        }
        if (r % 2 == 1) {
            tree[r - 1] += val;
            tree2[r - 1] ++;
        }
        l /= 2;
        r /= 2;
    }
}

pii query(int v) {
    v += base;
    int ans = 0;
    int ans2 = 0;
    while (v) {
        ans += tree[v];
        ans2 += tree2[v];
        v /= 2;
    }
    return {ans, ans2};
}


LCA lca;

struct zap{
    int a, b, g, s, idx, left, right, mid, koszts, ile;
};


bool comps(zap a, zap b) {
    return a.s < b.s;
}

bool comp_bin(zap a, zap b) {
    if (a.mid == b.mid) return a.idx < b.idx;
    return a.mid < b.mid;
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q, a, b;
    cin >> n >> m >> q;
    vector<vi> graf(n);
    vector<pii> kra;
    vi ile_bramek(n + 2, 0);

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--;
        b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
        kra.push_back({a, b});
    }
    lca.init(n, graf);
    vector<zap> tab_zap;

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--;
        zap z;
        z.a = kra[a].first;
        z.b = kra[a].second;
        if (lca.depth[z.a] > lca.depth[z.b]) swap(z.a, z.b);
        ile_bramek[lca.preorder[z.b]] ++;
        ile_bramek[lca.max_pre[z.b] + 1] --;
        z.idx = -1;
        z.mid = b;
        z.s = b;
        tab_zap.push_back(z);
    }

    sort(tab_zap.begin(), tab_zap.end(), comps);
    for (int i = 0; i < m; i++) {
        tab_zap[i].mid = i;
    }

    for (int i = 1; i < n + 2; i++) ile_bramek[i] += ile_bramek[i - 1];
    
    for (int i = 0; i < q; i++) {
        zap z;
        cin >> z.a >> z.b >> z.g >> z.s;
        z.a--;
        z.b--;
        z.idx = i;
        z.left = -1;
        z.right = m - 1;
        z.mid = (z.left + z.right + 1) / 2;
        tab_zap.push_back(z);
    }   
    vi odp(q, -1);

    for (int i = 0; i < 21; i++) {
        //cout << "UWU\n";
        tree.assign(2 * base, 0);
        tree2.assign(2 * base, 0);
        sort(tab_zap.begin(), tab_zap.end(), comp_bin);

        for (auto & z : tab_zap) {
            //if (z.idx == -1) cout << "Dodaje bariere: " << z.a << ' ' << z.b << ' ' << z.g << ' ' << z.s << ' ' << z.mid << '\n';
            //else cout << "Zapytanie: " << z.a << ' ' << z.b << ' ' << z.idx << ' ' << z.left << ' ' << z.right << ' ' << z.mid << '\n';
            if (z.idx == -1) {
                add(lca.preorder[z.b], lca.max_pre[z.b], z.s);
            }
            else {
                int prea = lca.preorder[z.a];
                int preb = lca.preorder[z.b];
                int lcaa = lca.lca(z.a, z.b);
                int prelca = lca.preorder[lcaa];
                //cout << query(prea).first << ' ' << query(preb).first << ' ' << query(prelca).first << '\n';

                long long koszt = query(prea).first + query(preb).first - 2 * query(prelca).first;
                z.koszts = koszt;
                z.ile = ile_bramek[prea] + ile_bramek[preb] - 2 * ile_bramek[prelca] - (query(prea).second + query(preb).second - 2 * query(prelca).second);
                if (koszt <= z.s) z.left = z.mid;
                else z.right = z.mid - 1;
                z.mid = (z.left + z.right + 1) / 2;
               // cout << "KOSZT: " << koszt << ' ' << z.ile << '\n';
                
                if (z.left == -1 && z.right == -1) z.mid = -1;
                if (z.koszts <= z.s && z.ile <= z.g) odp[z.idx] = z.g - z.ile;
                else odp[z.idx] = -1;
            }
        }
    }
    
    for (int i = 0; i < q; i++) {
        cout << odp[i] << '\n';
    }
    

    return 0;
}


/*
3 2 1
2 1
3 2
2 1
1 1
1 2 1 1*/

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