Submission #886313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886313	2023-12-11T19:30:56 Z	Hostek	Two Currencies (JOI23_currencies)	C++17	0 / 100	5000 ms	175952 KB

currencies

// https://oj.uz/problem/view/JOI23_currencies

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 400 * 1001, L = 17, INF = 1000 * 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

// #define DONOTX true

typedef vec<vec<int>> _kra;
typedef ar<int, 8 * sizik> TreeTD;

std::vector<ar<int, 2>> kra[sizik];
ar<int, 2> kraw_[sizik];
int ans[sizik];

int depth[sizik], pre[sizik], post[sizik], timer = 1;
ar<int, L + 1> up[sizik], IleNaG[sizik];

int jump(int temp_w, int temp_u) {
    for (int i = 0; i <= L; i++) {
        if (temp_u & (1 << i)) {
            temp_w = up[temp_w][i];
        }
    }
    return temp_w;
}

int pow2m1(int a) {
    return (1 << a) - 1;
}

vector<int> EulerTourVertices, EulerTourEdges;

int Ile[sizik];

void DFS(int v, int p, int czk) {
    // printf("was: %d\n", v);

    depth[v] = depth[p] + 1;

    pre[v] = ++timer;

    up[v][0] = p;
    for (int i = 1; i <= L; ++i)
        up[v][i] = up[up[v][i - 1]][i - 1];

    // std::cout << v << " " << p << " " << czk << '\n';

    IleNaG[v][0] = czk;
    for (int i = 1; i <= L; ++i) {
        IleNaG[v][i] = IleNaG[v][i - 1] + IleNaG[up[v][i - 1]][i - 1];
    }

    EulerTourVertices.push_back(v);
    for (const auto& [u, i] : kra[v]) {
        // printf("%d %d\n", v, u);
        if (u != p) {
            EulerTourEdges.push_back(i);
            DFS(u, v, Ile[i]);
            EulerTourEdges.push_back(i);
            EulerTourVertices.push_back(v);
        }
    }

    post[v] = ++timer;
}

bool is_ancestor(int u, int v) {
    return pre[u] <= pre[v] && post[u] >= post[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = L; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

int gn_helper(int v, int l) {
    int wyn = 0;

    // if (depth[l] > depth[v]) {
    //     std::swap(l, v);
    // }

    for (int i = L; i >= 0; --i) {
        if (!is_ancestor(up[v][i], l)) {
            // std::cout << "hello\n";
            // std::cout << "v,i ~> " << v << " " << i << '\n';

            wyn += IleNaG[v][i];
            v = up[v][i];
        }
    }

    if (v != l) {
        // std::cout << "ok " << IleNaG[v][0] << '\n';
        wyn += IleNaG[v][0];
    }

    return wyn;
}

int getNum(int v1, int v2) {
    int l = lca(v1, v2);

    // std::cout << v1 << " " << v2 << " lca ~> " << l << '\n';

    int tmp1 = gn_helper(v1, l);
    int tmp2 = gn_helper(v2, l);

    // std::cout << "1,2  ~> " << tmp1 << ' ' << tmp2 << '\n';

    return tmp1 + tmp2;
}

TreeTD tree1, tree2, tree3, tree4;
ar<int, sizik> first, first1, first2;

void query_prepare(int n) {
    // first.assign(n, -1);
    for (int i = 0; i <= n; i++) {
        first[i] = -1;
        first1[i] = -1;
        first2[i] = -1;
    }

    for (int i = 0; i < (int)EulerTourVertices.size(); ++i) {
        int v = EulerTourVertices[i];
        if (first[v] == -1) first[v] = i + 1;
    }

    for (int i = 0; i < (int)EulerTourEdges.size(); ++i) {
        int j = EulerTourEdges[i];
        if (first1[j] == -1)
            first1[j] = i + 1;
        else
            first2[j] = i + 1;
    }
}

int ll = 1;

void wypisz(int ll, const TreeTD& d) {
    int lvl = 2;
    int przerwa = ll - 1;
    for (int i = 1; i < 2 * ll; i++) {
        if (i == lvl) {
            lvl *= 2;
            std::cout << '\n';
            przerwa /= 2;
        }
        for (int j = 1; j <= przerwa; j++)
            std::cout << ' ';
        std::cout << d[i];
        for (int j = 1; j <= przerwa; j++)
            std::cout << ' ';
        std::cout << " ";
    }
    std::cout << '\n';
}

void sum_tree_update(TreeTD& d, int v, int a) {
    v += ll - 1;
    d[v] = a;
    while (v > 1) {
        v /= 2;
        d[v] = d[2 * v] + d[2 * v + 1];
    }
}

int sum_tree_query(const TreeTD& d, int o, int x, int y, int A, int B) {
    if (A <= x && y <= B) {
        return d[o];
    } else if (B < x || y < A) {
        return 0;
    } else {
        return sum_tree_query(d, o * 2, x, (x + y) / 2, A, B) + sum_tree_query(d, o * 2 + 1, (x + y) / 2 + 1, y, A, B);
    }
}

int query(int v1, int v2) {
    // std::cout << EulerTourEdges.size() << '\n';

    int t1 = sum_tree_query(tree1, 1, 1, ll, first[v1], first[v2] - 1), t2 = sum_tree_query(tree2, 1, 1, ll, first[v1], first[v2] - 1);

    // std::cout << "firsty : " << first[v1] << " " << first[v2] << '\n';
    // std::cout << "t1: " << t1 << " " << t2 << "\n";

    // std::cout << "Nasze drzewka\n1\n";
    // wypisz(ll, tree1);
    // std::cout << "2\n";
    // wypisz(ll, tree2);

    return t1 - t2;
}

int query1(int v1, int v2) {
    // std::cout << EulerTourEdges.size() << '\n';

    return sum_tree_query(tree3, 1, 1, ll, first[v1], first[v2] - 1) - sum_tree_query(tree4, 1, 1, ll, first[v1], first[v2] - 1);
}

int Lazy_query(int v1, int v2) {
    int l = lca(v1, v2);
    // std::cout << "lazy_q (lca) ~> " << l << '\n';

    // std::cout << v1 << " " << v2 << " | lca: " << l << "\n";
    // std::cout << first[v1] << " " << first[v2] << " | lca: " << first[l] << "\n";

    int tmp1 = query(l, v1);

    // std::cout << "af q1\n";

    int tmp2 = query(l, v2);

    // std::cout << "YAY\n";

    // std::cout << tmp1 << " " << tmp2 << '\n';

    return tmp1 + tmp2;
}

int Lazy_query1(int v1, int v2) {
    int l = lca(v1, v2);
    // std::cout << "lazy_q (lca) ~> " << l << '\n';

    int tmp1 = query1(l, v1);

    // std::cout << "af q1\n";

    int tmp2 = query1(l, v2);

    // std::cout << "YAY\n";

    // std::cout << "tmp ~> " << tmp1 << " " << tmp2 << '\n';

    return tmp1 + tmp2;
}

void update(int x, int a) {
    sum_tree_update(tree1, first1[x], a);
    sum_tree_update(tree2, first2[x], a);
}

void update1(int x, int a) {
    sum_tree_update(tree3, first1[x], a);
    sum_tree_update(tree4, first2[x], a);
}

vec<int> mids[sizik];
ar<int, 2> pk[sizik];

int midFunc(int gp, int gk) {
    return (gp + gk + 1) / 2;
}
void success(int& gp, int& gk, const int gm) {
    gp = gm;
}
void failure(int& gp, int& gk, const int gm) {
    gk = gm - 1;
}
void autoCheck(bool c, int& gp, int& gk, const int gm) {
    if (c) {
        success(gp, gk, gm);
    } else {
        failure(gp, gk, gm);
    }
}

void clear() {
    for (int i = 0; i < (int)tree1.size(); i++) {
        tree1[i] = 0;
        tree2[i] = 0;
        tree3[i] = 0;
        tree4[i] = 0;
    }
}

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;

    while (ll <= n) {
        ll *= 2;
    }

    for (int i = 1; i <= n - 1; i++) {
        auto& [a, b] = kraw_[i];
        std::cin >> a >> b;

        kra[a].push_back({b, i});
        kra[b].push_back({a, i});
    }

    std::vector<ar<int, 2>> CP(m);
    for (auto& [C, P] : CP) {
        std::cin >> P >> C;

        Ile[P]++;

        // kraw[P] ~> C srebrników
    }

    DFS(1, 1, 0);

    query_prepare(n);

    // std::cout << "EulerTourEdges: ";
    // for (int i = 0; i < (int)EulerTourEdges.size(); i++) {
    //     std::cout << EulerTourEdges[i] << ' ';
    // }
    // std::cout << '\n';

    // std::cout << "EulerTourVertices: ";
    // for (int i = 0; i < (int)EulerTourVertices.size(); i++) {
    //     std::cout << EulerTourVertices[i] << ' ';
    // }
    // std::cout << '\n';

    // std::cout << "first: ";
    // for (int i = 1; i <= n; i++) {
    //     std::cout << first[i] << ' ';
    // }
    // std::cout << '\n';

    // std::cout << "first1: ";
    // for (int i = 1; i <= n; i++) {
    //     std::cout << first1[i] << ' ';
    // }
    // std::cout << '\n';

    // std::cout << "first2: ";
    // for (int i = 1; i <= n; i++) {
    //     std::cout << first2[i] << ' ';
    // }
    // std::cout << '\n';

    // for (int i = 1; i <= n; i++) {
    //     std::cout << i << " ~> ";
    //     for (int j = 0; j <= L; j++) {
    //         std::cout << IleNaG[i][j] << " ";
    //     }
    //     std::cout << '\n';
    // }

    std::sort(CP.begin(), CP.end());

    std::vector<ar<int, 3>> mieszkancy(q + 1);

    for (int i = 1; i <= q; ++i) {
        auto& [s, t, y] = mieszkancy[i];
        std::cin >> s >> t >> ans[i] >> y;

        int x = getNum(s, t);
        // ans[i] += x;
        ans[i] -= x;
        // std::cout << "i ~> " << i << "  x: " << x << " | ans pered ~> " << ans[i] << '\n';
    }

    int gp = 0, gk = m;
    const int gm = midFunc(gp, gk);
    for (int i = 1; i <= q; i++) {
        // mids[i] = midFunc(gp, gk);
        mids[gm].push_back(i);
        pk[i] = {gp, gk};
    }

    int zostalo = q;

    while (zostalo) {
        // std::cout << zostalo << '\n';

        for (int i = 0; i <= m; i++) {
            if (i != 0) {
                // dodaj tam, co trzeba i-te
                // std::cout << "up bef\n";
                update(CP[i - 1][1], CP[i - 1][0]);
                update1(CP[i - 1][1], 1);
                // std::cout << "up af\n";

                // std::cout << "1\n";
                // wypisz(ll, tree1);
                // std::cout << "2\n";
                // wypisz(ll, tree2);
                // std::cout << "3\n";
                // wypisz(ll, tree3);
                // std::cout << "4\n";
                // wypisz(ll, tree4);
            }

            for (const auto& u : mids[i]) {
                auto& [p, k] = pk[u];

                // std::cout << "bef lazy query\n";
                const int local_sum = Lazy_query(mieszkancy[u][0], mieszkancy[u][1]);

                if (p >= k) {
                    // ziomek nie ma wyjscia (usuwan);
                    // ans[u] -= p;
                    int value = Lazy_query1(mieszkancy[u][0], mieszkancy[u][1]);

                    // std::cout << "value: " << value << '\n';

                    ans[u] += value;

                    // std::cout << "h: " << u << " " << p << "  | v: " << value << " || nasze koszta(nasz ziomek, wtóry ziomek: )" <<
                    // mieszkancy[u][2]
                    //   << " " << local_sum << '\n';

                    zostalo--;
                    continue;
                }

                // std::cout << "mid = " << i << "  " << u << '\n';
                // std::cout << "wtf: " << mieszkancy[u][2] << ' ' << local_sum << "\n";

                if (mieszkancy[u][2] >= local_sum) {
                    success(p, k, i);
                } else {
                    failure(p, k, i);
                }

                // std::cout << "klasik ~> " << p << " " << k << " " << u << '\n';

                if (p >= k) {
                    mids[p].push_back(u);
                } else {
                    mids[midFunc(p, k)].push_back(u);
                }
            }

            mids[i].clear();
            mids[i].shrink_to_fit();
        }

        clear();
    }

    for (int i = 1; i <= q; i++) {
        // std::cout << "real ans ~> " << ans[i] << " || ";
        std::cout << std::max(-1, ans[i]) << '\n';
    }
}

int32_t main() {
#ifndef DONOTX
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}

/*

for (const auto& u : mids[0]) {
    // jakiś gościu ma mida w zerze ;)
    // oczywiscie moze (Q = 0)

    auto& [p, k] = pk[u];

    success(p, k, 0);

    if (p >= k) {
        // ziomek nie ma wyjscia (usuwan);
        ans[u] -= p;

        zostalo--;
    } else {
        mids[midFunc(p, k)].push_back(u);
    }
}

*/

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	86868 KB	Output is correct
2	Runtime error	86 ms	175952 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	94 ms	175856 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5067 ms	86872 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	86868 KB	Output is correct
2	Runtime error	86 ms	175952 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-