Submission #975471

#	Time	Username	Problem	Language	Result	Execution time	Memory
975471		green_gold_dog	Two Currencies (JOI23_currencies)	C++17	100 / 100	2288 ms	78720 KiB

currencies

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 20;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

struct BIT {
        vector<ll> tree;
        BIT(ll n) {
                tree.resize(n + 1, 0);
        }
        ll get(ll x) {
                ll ans = 0;
                for (; x > 0; x -= x & -x) {
                        ans += tree[x];
                }
                return ans;
        }
        void add(ll x, ll y) {
                x++;
                for (; x < tree.size(); x += x & -x) {
                        tree[x] += y;
                }
        }
        void clear() {
                for (auto& i : tree) {
                        i = 0;
                }
        }
};

struct LCA {
        vector<vector<ll>> binup;
        vector<ll> h;
        LCA(vector<vector<ll>>& tree) {
                binup.resize(LOG, vector<ll>(tree.size(), 0));
                h.resize(tree.size(), -1);
                dfs(0, 0, tree);
        }
        void dfs(ll v, ll p, vector<vector<ll>>& tree) {
                h[v] = h[p] + 1;
                binup[0][v] = p;
                for (ll i = 1; i < LOG; i++) {
                        binup[i][v] = binup[i - 1][binup[i - 1][v]];
                }
                for (auto i : tree[v]) {
                        if (i != p) {
                                dfs(i, v, tree);
                        }
                }
        }
        ll get_LA(ll v, ll x) {
                for (ll i = 0; i < LOG; i++) {
                        if ((x >> i) & 1) {
                                x -= 1 << i;
                                v = binup[i][v];
                        }
                }
                return v;
        }
        ll get(ll a, ll b) {
                if (h[a] < h[b]) {
                        swap(a, b);
                }
                a = get_LA(a, h[a] - h[b]);
                if (a == b) {
                        return a;
                }
                for (ll i = LOG - 1; i >= 0; i--) {
                        if (binup[i][a] != binup[i][b]) {
                                a = binup[i][a];
                                b = binup[i][b];
                        }
                }
                return binup[0][a];
        }
};

void dfs(ll v, ll p, vector<vector<ll>>& tree, BIT& bi, BIT& bc, vector<vector<pair<ll, ll>>>& cs, vector<vector<pair<ll, ll>>>& qs, vector<pair<ll, ll>>& ans, ll nc) {
        for (auto[a, b] : cs[v]) {
                bi.add(a, b);
                bc.add(a, 1);
                nc++;
        }
        for (auto i : tree[v]) {
                if (i != p) {
                        dfs(i, v, tree, bi, bc, cs, qs, ans, nc);
                }
        }
        for (auto[a, b] : qs[v]) {
                ans[b].first = bi.get(a);
                ans[b].second = nc - bc.get(a);
        }
        for (auto[a, b] : cs[v]) {
                bi.add(a, -b);
                bc.add(a, -1);
        }
}

void solve() {
        ll n, m, q;
        cin >> n >> m >> q;
        vector<vector<ll>> tree(n);
        vector<pair<ll, ll>> rs;
        for (ll i = 1; i < n; i++) {
                ll a, b;
                cin >> a >> b;
                a--;
                b--;
                rs.emplace_back(a, b);
                tree[a].push_back(b);
                tree[b].push_back(a);
        }
        LCA l(tree);
        vector<ll> pred;
        for (auto[a, b] : rs) {
                pred.push_back((l.get(a, b) == a ? b : a));
        }
        vector<vector<pair<ll, ll>>> cs(n);
        vector<pair<ll, ll>> all;
        for (ll i = 0; i < m; i++) {
                ll p, c;
                cin >> p >> c;
                p--;
                p = pred[p];
                all.emplace_back(c, p);
        }
        sort(all.begin(), all.end());
        for (ll i = 0; i < m; i++) {
                cs[all[i].second].push_back(make_pair(i, all[i].first));
        }
        vector<tuple<ll, ll, ll, ll, ll, ll, ll>> qs;
        vector<ll> ans;
        for (ll i = 0; i < q; i++) {
                ll s, t, x, y;
                cin >> s >> t >> x >> y;
                s--;
                t--;
                qs.emplace_back(0, m + 1, s, t, l.get(s, t), y, x);
                ans.push_back(x + 1);
        }
        for (ll _ = 0; _ < LOG; _++) {
                vector<vector<pair<ll, ll>>> nqs(n);
                vector<pair<ll, ll>> anss(q * 3);
                BIT bi(m), bc(m);
                for (ll i = 0; i < q; i++) {
                        auto[l, r, s, t, lca, y, x] = qs[i];
                        ll mid = (l + r) / 2;
                        nqs[s].emplace_back(mid, i * 3);
                        nqs[t].emplace_back(mid, i * 3 + 1);
                        nqs[lca].emplace_back(mid, i * 3 + 2);
                }
                dfs(0, 0, tree, bi, bc, cs, nqs, anss, 0);
                for (ll i = 0; i < q; i++) {
                        ll na = anss[i * 3].first + anss[i * 3 + 1].first - anss[i * 3 + 2].first * 2;
                        auto&[l, r, s, t, lca, y, x] = qs[i];
                        ll mid = (l + r) / 2;
                        if (na > y) {
                                r = mid;
                        } else {
                                l = mid;
                                assign_min(ans[i], anss[i * 3].second + anss[i * 3 + 1].second - anss[i * 3 + 2].second * 2);
                        }
                }
        }
        for (ll i = 0; i < q; i++) {
                cout << get<6>(qs[i]) - ans[i] << '\n';
        }
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message (stderr)

currencies.cpp: In member function 'void BIT::add(ll, ll)':
currencies.cpp:64:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 for (; x < tree.size(); x += x & -x) {
      |                        ~~^~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:216:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
currencies.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

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