Submission #1273166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273166		hiepsimauhong	Two Currencies (JOI23_currencies)	C++20	100 / 100	3053 ms	68680 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ll = long long;

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A,L,R) FOR(OK, L, R){if(A[OK]<=-oo / 10||A[OK]>=oo)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 0, L){FOR(KO, 0, R){if(A[OK][KO]>-oo&&A[OK][KO]<oo)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';

#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define div alksdjf

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;

int n, m, q;
vector<int> g[N];
ii edge[N], sta[N];
vector<int> result[N];

int s[N], t[N], w[N];
int gold[N], silver[N];

struct Segment_tree{
        int sg[N << 2];

        void reset(){
                memset(sg, 0, sizeof sg);
        }

        void update(int id, int l, int r, int pos, int val){
                if(l > pos || r < pos){
                        return;
                }
                if(l == r){
                        sg[id] += val;
                        return;
                }

                int mid = (l + r) >> 1;

                update(id << 1, l, mid, pos, val);
                update(id << 1 | 1, mid + 1, r, pos, val);

                sg[id] = sg[id << 1] + sg[id << 1 | 1];
        }

        int get(int id, int l, int r, int u, int v){
                if(l > v || r < u){
                        return 0;
                }
                if(u <= l && r <= v){
                        return sg[id];
                }

                int mid = (l + r) >> 1;
                return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
        }
} sg;

struct HeavyLight{
        int el;
        int nxt[N], top[N], sz[N], parent[N];
        int st[N], en[N], h[N];

        void DFS(int u, int par){
                sz[u] = 1;

                FOA(v, g[u]){
                        if(v == par){
                                continue;
                        }
                        parent[v] = u;
                        h[v] = h[u] + 1;
                        DFS(v, u);

                        sz[u] += sz[v];

                        if(sz[nxt[u]] < sz[v]){
                                nxt[u] = v;
                        }
                }
        }

        void HLD(int u, int par, int tp){
                st[u] = ++el;
                top[u] = tp;

                if(nxt[u]){
                        HLD(nxt[u], u, tp);
                }

                FOA(v, g[u]){
                        if(v == par || v == nxt[u]){
                                continue;
                        }
                        HLD(v, u, v);
                }

                en[u] = el;
        }

        int LCA(int u, int v){
                while(top[u] != top[v]){
                        if(h[top[u]] < h[top[v]]){
                                swap(u, v);
                        }
                        u = parent[top[u]];
                }
                if(h[u] > h[v]) swap(u, v);
                return u;
        }

        int path(int u, int v){
                int res = 0;
                while(top[u] != top[v]){
                        if(h[top[u]] < h[top[v]]){
                                swap(u, v);
                        }
                        res += sg.get(1, 1, n, st[top[u]], st[u]);
                        u = parent[top[u]];
                }
                if(h[u] > h[v]) swap(u, v);
                res += sg.get(1, 1, n, st[u] + 1, st[v]);

                return res;
        }
} hld;

namespace BinarySearch{
        int L[N], R[N], ans[N];
        vector<int> query[N];

        void working(){
                FOR(mid, 1, m){
                        int u = sta[mid].sd, cost = sta[mid].fs;
                        sg.update(1, 1, n, hld.st[u], cost);

                        FOA(i, query[mid]){
                                int get = hld.path(s[i], t[i]);

                                if(get <= silver[i]){
                                        L[i] = mid + 1;
                                        ans[i] = mid;
                                }
                                else{
                                        R[i] = mid - 1;
                                }
                        }
                        query[mid].clear();
                }
        }

        void solve(){
                FOR(i, 1, q){
                        L[i] = 1, R[i] = m;
                }
                FOR(times, 1, 20){
                        sg.reset();
                        FOR(i, 1, q){
                                if(L[i] <= R[i]){
                                        query[L[i] + R[i] >> 1].push_back(i);
                                }
                        }

                        working();
                }
        }
} using namespace BinarySearch;

void AllPath(){
        sg.reset();
        FOR(i, 1, m){
                int u = sta[i].sd;
                sg.update(1, 1, n, hld.st[u], 1);

                FOA(v, result[i]){
                        w[v] = hld.path(s[v], t[v]);
                }
        }

        FOR(i, 1, q){
                int cost = hld.path(s[i], t[i]);

                if(cost - w[i] <= gold[i]){
                        cout << gold[i] - cost + w[i] << '\n';
                }
                else{
                        cout << -1 << '\n';
                }
        }
}


signed main(){ quickly
        cin >> n >> m >> q;

        FOR(i, 1, n - 1){
                int u, v;
                cin >> u >> v;
                edge[i] = {u, v};
                g[u].push_back(v);
                g[v].push_back(u);
        }

        hld.DFS(1, -1);
        hld.HLD(1, -1, 1);

        FOR(i, 1, m){
                int x, c;
                cin >> x >> c;

                int u = edge[x].fs, v = edge[x].sd;

                if(hld.st[u] > hld.st[v]){
                        swap(u, v);
                }

                sta[i] = {c, v};
        }

        sort(sta + 1, sta + 1 + m);

        FOR(i, 1, q){
                cin >> s[i] >> t[i] >> gold[i] >> silver[i];
        }

        solve();

        FOR(i, 1, q){
                result[ans[i]].push_back(i);
        }

        AllPath();
}

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