Submission #847851

#	Time	Username	Problem	Language	Result	Execution time	Memory
847851		fanwen	Two Currencies (JOI23_currencies)	C++17	100 / 100	2772 ms	256416 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

struct Data {
    long long sumC = 0, cnt = 0;
    Data(long long sumC = 0, int cnt = 0) : sumC(sumC), cnt(cnt) {}

    Data operator + (const Data &a) const { return Data(sumC + a.sumC, cnt + a.cnt); }
    Data operator - (const Data &a) const { return Data(sumC - a.sumC, cnt - a.cnt); }

    Data & operator += (const Data &a) { return *this = *this + a; }
    Data & operator -= (const Data &a) { return *this = *this - a; }
    friend ostream & operator << (ostream &out, const Data &x) { return out << "(" << x.sumC << ", " << x.cnt << ")"; }
};

template <class T>
struct Persistent {
    struct node {
        T val;
        int l, r;
        node (T val = {}, int l = 0, int r = 0) : val(val), l(l), r(r) {}
    };
    vector <node> it;
    vector <int> stt;
    int n, version;

private : 
    void update(int idx, int l, int r, int u, T val) {
        if(l > u || r < u) return;
        int cnt = ++version;
        stt[idx] = cnt;
        if(l == r) {
            it[cnt].val = val;
            return;
        }
        int mid = l + r >> 1;
        update(idx << 1, l, mid, u, val);
        update(idx << 1 | 1, mid + 1, r, u, val);
        it[cnt] = node(it[stt[idx << 1]].val + it[stt[idx << 1 | 1]].val, stt[idx << 1], stt[idx << 1 | 1]);
    }

    T get(int idx, int l, int r, int u, int v) {
        if(l > v || r < u) return T{};
        if(l >= u && r <= v) return it[idx].val;
        int mid = l + r >> 1;
        return get(it[idx].l, l, mid, u, v) + get(it[idx].r, mid + 1, r, u, v);
    }
public :
    
    Persistent(int n = 0) : n(n) {
        version = 0;
        resize(n);
    }

    void resize(int _n) {
        n = _n;
        it.resize(100 * n + 1);
        stt.resize(n << 2 | 1);
    }

    int update(int u, T val) {
        update(1, 1, n, u, val);
        return stt[1];
    }

    T get(int id, int l, int r) {
        return get(id, 1, n, l, r);
    }

    int size() {
        return n;
    }
};

const int MAXN = 1e5 + 5;

int N, M, Q;

int local[MAXN], header[MAXN], depth[MAXN], par[MAXN], numChild[MAXN];
vector <int> adj[MAXN];

void dfs(int u, int p) {
    par[u] = p;
    numChild[u] = 1;
    int id = 0, Max = 0;
    REP(i, (int) adj[u].size()) if(adj[u][i] != p) {
        dfs(adj[u][i], u);
        numChild[u] += numChild[adj[u][i]];
        if(maximize(Max, numChild[adj[u][i]])) id = i;
    }
    swap(adj[u][0], adj[u][id]);
}
void HLD(int u) {
    static int run = 0;
    local[u] = ++run;
    REP(i, (int) adj[u].size()) if(adj[u][i] != par[u]) {
        if(i == 0 && 2 * numChild[adj[u][i]] >= numChild[u]) header[adj[u][i]] = header[u], depth[adj[u][i]] = depth[u];
        else header[adj[u][i]] = adj[u][i], depth[adj[u][i]] = depth[u] + 1;
        HLD(adj[u][i]);
    }
}
    
Persistent <Data> it;

int root[MAXN];

Data get(int u, int v, int id) {
    Data ans;
    if(depth[u] < depth[v]) swap(u, v);
    while(depth[u] > depth[v]) {
        ans += it.get(id, local[header[u]], local[u]);
        u = par[header[u]];
    }
    while(header[u] != header[v]) {
        ans += it.get(id, local[header[u]], local[u]);
        ans += it.get(id, local[header[v]], local[v]);
        u = par[header[u]];
        v = par[header[v]];
    }
    if(local[u] > local[v]) swap(u, v);
    ans += it.get(id, local[u] + 1, local[v]);
    return ans;
}

void you_maadj_it(void) {
    cin >> N >> M >> Q;
    vector <pair <int, int>> edges(N - 1);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    it.resize(N);
    vector <pair <int, int>> checkpoints(M);
    for (auto &[c, p] : checkpoints) cin >> p >> c, p--;
    sort(ALL(checkpoints));
    dfs(1, 0); depth[1] = header[1] = 1; HLD(1);
    REP(i, M) {
        auto [c, p] = checkpoints[i];
        auto &[u, v] = edges[p];
        if(v == par[u]) swap(u, v);
        Data res = (i == 0 ? Data(0, 0) : it.get(root[i], local[v], local[v]));
        res += Data(c, 1);
        root[i + 1] = it.update(local[v], res);
    }

    FOR(i, 1, Q) {
        int s, t, x; long long y; cin >> s >> t >> x >> y;
        int l = 0, r = M + 1;
        Data res = get(s, t, root[M]);
        while(r - l > 1) {
            int mid = l + r >> 1;
            if(get(s, t, root[mid]).sumC <= y) l = mid;
            else r = mid;
        }
        res -= get(s, t, root[l]);
        int rem = x - res.cnt;
        cout << max(rem, -1) << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_maadj_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

currencies.cpp: In function 'void you_maadj_it()':
currencies.cpp:166:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |             int mid = l + r >> 1;
      |                       ~~^~~
currencies.cpp: In instantiation of 'T Persistent<T>::get(int, int, int, int, int) [with T = Data]':
currencies.cpp:81:19:   required from 'T Persistent<T>::get(int, int, int) [with T = Data]'
currencies.cpp:125:53:   required from here
currencies.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = l + r >> 1;
      |                   ~~^~~
currencies.cpp: In instantiation of 'void Persistent<T>::update(int, int, int, int, T) [with T = Data]':
currencies.cpp:76:15:   required from 'int Persistent<T>::update(int, T) [with T = Data]'
currencies.cpp:158:46:   required from here
currencies.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~

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