Submission #1055361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055361		fryingduc	Two Currencies (JOI23_currencies)	C++17	100 / 100	675 ms	41512 KiB

currencies

#include "bits/stdc++.h"
using namespace std;
 
const int maxn = 1e5 + 5;
int n, m, q;
vector<int> g[maxn];
int edge_u[maxn], edge_v[maxn];
int p[maxn];
long long c[maxn];
int s[maxn], t[maxn];
long long x[maxn], y[maxn];
int le[maxn], ri[maxn], res[maxn];
int cur_pos, pos[maxn], head[maxn];
int sz[maxn], h[maxn], par[maxn];
int ord[maxn];
vector<int> cand[maxn];
 
struct fenwick_tree {
    #define gb(x) (x) & (-x)
    int n;
    vector<long long> bit;
    fenwick_tree() {}
    fenwick_tree(int n) : n(n), bit(n + 5, 0) {}
    void update(int x, long long val) {
        for(int i = x; i <= n; i += gb(i)) bit[i] += val;
    }
    long long get(int x) {
        long long ans = 0;
        for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
        return ans;
    }
    long long get(int l, int r) {
        if(l > r) return 0;
        return get(r) - get(l - 1);
    }
} fen, fen_cnt;
void pre_dfs(int u, int prev) {
    sz[u] = 1;
    for(auto v:g[u]) {
        if(v == prev) continue;
        h[v] = h[u] + 1;
        par[v] = u;
        pre_dfs(v, u);
        sz[u] += sz[v];
    }
}
void hld(int u, int prev) {
    if(!head[u]) {
        head[u] = u;
    }
    pos[u] = ++cur_pos;
    int big_child = -1;
    for(auto v:g[u]) {
        if(v == prev) continue;
        if(big_child == -1 || sz[big_child] < sz[v]) big_child = v;
    }
    if(big_child != -1) {
        head[big_child] = head[u];
        hld(big_child, u);
    }
    for(auto v:g[u]) {
        if(v == prev || v == big_child) continue;
        hld(v, u);
    }
}
void update(int u, long long val) {
    fen.update(pos[u], val);
}
void update_cnt(int u) {
    fen_cnt.update(pos[u], 1);
}
long long get(int u, int v) {
    long long ans = 0;
    while(head[u] != head[v]) {
        if(h[head[u]] > h[head[v]]) swap(u, v);
        ans += fen.get(pos[head[v]], pos[v]);
        v = par[head[v]];
    }
    if(h[u] > h[v]) swap(u, v);
    ans += fen.get(pos[u] + 1, pos[v]);
    return ans;
}
int get_cnt(int u, int v) {
    int ans = 0;
    while(head[u] != head[v]) {
        if(h[head[u]] > h[head[v]]) swap(u, v);
        ans += fen_cnt.get(pos[head[v]], pos[v]);
        v = par[head[v]];
    }
    if(h[u] > h[v]) swap(u, v);
    ans += fen_cnt.get(pos[u] + 1, pos[v]);
    return ans;
}
void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge_u[i] = u, edge_v[i] = v;
    }
    for(int i = 1; i <= m; ++i) {
        cin >> p[i] >> c[i];
        ord[i] = i;
    }
    for(int i = 1; i <= q; ++i) {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        le[i] = 1, ri[i] = m;
    }
    par[1] = h[1] = 1;
    pre_dfs(1, 0);
    hld(1, 0);
    
    for(int i = 1; i < n; ++i) {
        if(par[edge_u[i]] == edge_v[i]) swap(edge_u[i], edge_v[i]);
    }
    sort(ord + 1, ord + m + 1, [](const int &x, const int &y) -> bool {
        return (c[x] != c[y] ? c[x] < c[y] : p[x] < p[y]); 
    });
    
    while(1) {
        bool exist = 0;
        for(int i = 1; i <= q; ++i) {
            if(le[i] <= ri[i]) {
                int mid = (le[i] + ri[i]) / 2;
                cand[mid].push_back(i);
                exist = 1;
            }
        }
        if(!exist) break;
        
        fen = fenwick_tree(n + 1);
        
        for(int mid = 1; mid <= m; ++mid) {
            update(edge_v[p[ord[mid]]], c[ord[mid]]);
            
            
            for(auto i:cand[mid]) {
                long long im_hungry = get(s[i], t[i]);
                if(im_hungry <= y[i]) {
                    res[i] = mid;
                    le[i] = mid + 1;
                }
                else {
                    ri[i] = mid - 1;
                }
            }
            
            cand[mid].clear();
        }
    }
    for(int i = 1; i <= q; ++i) {
        cand[res[i]].push_back(i);
    }
    fen_cnt = fenwick_tree(n + 1);
    for(int i = m; i >= 0; --i) {
        for(auto j:cand[i]) {
            res[j] = x[j] - get_cnt(s[j], t[j]);
        }
        if(i) update_cnt(edge_v[p[ord[i]]]);
    }
    for(int i = 1; i <= q; ++i) {
        cout << (res[i] < 0 ? -1 : res[i]) << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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