oj.uz

Submission #847844

# Submission time Handle Problem Language Result Execution time Memory
847844 2023-09-10T15:10:37 Z fanwen Two Currencies (JOI23_currencies) C++17
100 / 100
 3109 ms 262216 KB 
#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;
        }
        // cout << "query i = " << i << '\n';
        // cout << get(s, t, root[l]) << endl;
        // cout << debug(res) << '\n';
        res -= get(s, t, root[l]);
        int rem = x - res.cnt;
        cout << max(rem, -1) << endl;
    }
}

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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 11 ms 9048 KB Output is correct
6 Correct 16 ms 9304 KB Output is correct
7 Correct 14 ms 7768 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 15 ms 9304 KB Output is correct
10 Correct 17 ms 9516 KB Output is correct
11 Correct 17 ms 9308 KB Output is correct
12 Correct 17 ms 9304 KB Output is correct
13 Correct 10 ms 9560 KB Output is correct
14 Correct 10 ms 9560 KB Output is correct
15 Correct 14 ms 9560 KB Output is correct
16 Correct 13 ms 9560 KB Output is correct
17 Correct 13 ms 9560 KB Output is correct
18 Correct 12 ms 9564 KB Output is correct
19 Correct 11 ms 9304 KB Output is correct
20 Correct 11 ms 9304 KB Output is correct
21 Correct 10 ms 9304 KB Output is correct
22 Correct 11 ms 9304 KB Output is correct
23 Correct 15 ms 9520 KB Output is correct
24 Correct 15 ms 9304 KB Output is correct
25 Correct 19 ms 9560 KB Output is correct
26 Correct 15 ms 9304 KB Output is correct
27 Correct 14 ms 9304 KB Output is correct
28 Correct 14 ms 9516 KB Output is correct
29 Correct 11 ms 9508 KB Output is correct
30 Correct 17 ms 9516 KB Output is correct
31 Correct 17 ms 9304 KB Output is correct
32 Correct 19 ms 9304 KB Output is correct
33 Correct 11 ms 9560 KB Output is correct
34 Correct 11 ms 9560 KB Output is correct
35 Correct 9 ms 9560 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 20 ms 9308 KB Output is correct
3 Correct 17 ms 9304 KB Output is correct
4 Correct 16 ms 9304 KB Output is correct
5 Correct 1742 ms 250972 KB Output is correct
6 Correct 2289 ms 169272 KB Output is correct
7 Correct 2083 ms 207144 KB Output is correct
8 Correct 1422 ms 216924 KB Output is correct
9 Correct 1413 ms 215632 KB Output is correct
10 Correct 2736 ms 251544 KB Output is correct
11 Correct 2660 ms 251728 KB Output is correct
12 Correct 2678 ms 251652 KB Output is correct
13 Correct 2698 ms 251704 KB Output is correct
14 Correct 2494 ms 251664 KB Output is correct
15 Correct 1142 ms 261200 KB Output is correct
16 Correct 1242 ms 261936 KB Output is correct
17 Correct 1186 ms 260720 KB Output is correct
18 Correct 2145 ms 252604 KB Output is correct
19 Correct 2180 ms 252672 KB Output is correct
20 Correct 2245 ms 252852 KB Output is correct
21 Correct 785 ms 251592 KB Output is correct
22 Correct 816 ms 251364 KB Output is correct
23 Correct 777 ms 251548 KB Output is correct
24 Correct 785 ms 251548 KB Output is correct
25 Correct 2190 ms 252284 KB Output is correct
26 Correct 2251 ms 252436 KB Output is correct
27 Correct 1923 ms 252000 KB Output is correct
28 Correct 1876 ms 251536 KB Output is correct
29 Correct 1627 ms 251664 KB Output is correct
30 Correct 2105 ms 251864 KB Output is correct
31 Correct 1858 ms 251908 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 10 ms 9564 KB Output is correct
3 Correct 9 ms 9560 KB Output is correct
4 Correct 10 ms 9560 KB Output is correct
5 Correct 673 ms 249000 KB Output is correct
6 Correct 656 ms 241068 KB Output is correct
7 Correct 938 ms 145404 KB Output is correct
8 Correct 1392 ms 261964 KB Output is correct
9 Correct 1339 ms 261876 KB Output is correct
10 Correct 1283 ms 262088 KB Output is correct
11 Correct 987 ms 262128 KB Output is correct
12 Correct 888 ms 262056 KB Output is correct
13 Correct 918 ms 261640 KB Output is correct
14 Correct 631 ms 261828 KB Output is correct
15 Correct 654 ms 261788 KB Output is correct
16 Correct 782 ms 262216 KB Output is correct
17 Correct 840 ms 261652 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 11 ms 9048 KB Output is correct
6 Correct 16 ms 9304 KB Output is correct
7 Correct 14 ms 7768 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 15 ms 9304 KB Output is correct
10 Correct 17 ms 9516 KB Output is correct
11 Correct 17 ms 9308 KB Output is correct
12 Correct 17 ms 9304 KB Output is correct
13 Correct 10 ms 9560 KB Output is correct
14 Correct 10 ms 9560 KB Output is correct
15 Correct 14 ms 9560 KB Output is correct
16 Correct 13 ms 9560 KB Output is correct
17 Correct 13 ms 9560 KB Output is correct
18 Correct 12 ms 9564 KB Output is correct
19 Correct 11 ms 9304 KB Output is correct
20 Correct 11 ms 9304 KB Output is correct
21 Correct 10 ms 9304 KB Output is correct
22 Correct 11 ms 9304 KB Output is correct
23 Correct 15 ms 9520 KB Output is correct
24 Correct 15 ms 9304 KB Output is correct
25 Correct 19 ms 9560 KB Output is correct
26 Correct 15 ms 9304 KB Output is correct
27 Correct 14 ms 9304 KB Output is correct
28 Correct 14 ms 9516 KB Output is correct
29 Correct 11 ms 9508 KB Output is correct
30 Correct 17 ms 9516 KB Output is correct
31 Correct 17 ms 9304 KB Output is correct
32 Correct 19 ms 9304 KB Output is correct
33 Correct 11 ms 9560 KB Output is correct
34 Correct 11 ms 9560 KB Output is correct
35 Correct 9 ms 9560 KB Output is correct
36 Correct 1 ms 4440 KB Output is correct
37 Correct 20 ms 9308 KB Output is correct
38 Correct 17 ms 9304 KB Output is correct
39 Correct 16 ms 9304 KB Output is correct
40 Correct 1742 ms 250972 KB Output is correct
41 Correct 2289 ms 169272 KB Output is correct
42 Correct 2083 ms 207144 KB Output is correct
43 Correct 1422 ms 216924 KB Output is correct
44 Correct 1413 ms 215632 KB Output is correct
45 Correct 2736 ms 251544 KB Output is correct
46 Correct 2660 ms 251728 KB Output is correct
47 Correct 2678 ms 251652 KB Output is correct
48 Correct 2698 ms 251704 KB Output is correct
49 Correct 2494 ms 251664 KB Output is correct
50 Correct 1142 ms 261200 KB Output is correct
51 Correct 1242 ms 261936 KB Output is correct
52 Correct 1186 ms 260720 KB Output is correct
53 Correct 2145 ms 252604 KB Output is correct
54 Correct 2180 ms 252672 KB Output is correct
55 Correct 2245 ms 252852 KB Output is correct
56 Correct 785 ms 251592 KB Output is correct
57 Correct 816 ms 251364 KB Output is correct
58 Correct 777 ms 251548 KB Output is correct
59 Correct 785 ms 251548 KB Output is correct
60 Correct 2190 ms 252284 KB Output is correct
61 Correct 2251 ms 252436 KB Output is correct
62 Correct 1923 ms 252000 KB Output is correct
63 Correct 1876 ms 251536 KB Output is correct
64 Correct 1627 ms 251664 KB Output is correct
65 Correct 2105 ms 251864 KB Output is correct
66 Correct 1858 ms 251908 KB Output is correct
67 Correct 2 ms 4440 KB Output is correct
68 Correct 10 ms 9564 KB Output is correct
69 Correct 9 ms 9560 KB Output is correct
70 Correct 10 ms 9560 KB Output is correct
71 Correct 673 ms 249000 KB Output is correct
72 Correct 656 ms 241068 KB Output is correct
73 Correct 938 ms 145404 KB Output is correct
74 Correct 1392 ms 261964 KB Output is correct
75 Correct 1339 ms 261876 KB Output is correct
76 Correct 1283 ms 262088 KB Output is correct
77 Correct 987 ms 262128 KB Output is correct
78 Correct 888 ms 262056 KB Output is correct
79 Correct 918 ms 261640 KB Output is correct
80 Correct 631 ms 261828 KB Output is correct
81 Correct 654 ms 261788 KB Output is correct
82 Correct 782 ms 262216 KB Output is correct
83 Correct 840 ms 261652 KB Output is correct
84 Correct 1829 ms 210508 KB Output is correct
85 Correct 1864 ms 138456 KB Output is correct
86 Correct 1645 ms 135440 KB Output is correct
87 Correct 3109 ms 252240 KB Output is correct
88 Correct 2916 ms 252204 KB Output is correct
89 Correct 2941 ms 251968 KB Output is correct
90 Correct 3044 ms 252376 KB Output is correct
91 Correct 2882 ms 251844 KB Output is correct
92 Correct 1545 ms 258640 KB Output is correct
93 Correct 1366 ms 260316 KB Output is correct
94 Correct 2514 ms 252312 KB Output is correct
95 Correct 2465 ms 252744 KB Output is correct
96 Correct 2531 ms 252256 KB Output is correct
97 Correct 2582 ms 254208 KB Output is correct
98 Correct 1455 ms 251744 KB Output is correct
99 Correct 1565 ms 251468 KB Output is correct
100 Correct 1583 ms 251456 KB Output is correct
101 Correct 1501 ms 251632 KB Output is correct
102 Correct 2375 ms 252076 KB Output is correct
103 Correct 2387 ms 252200 KB Output is correct
104 Correct 2348 ms 252292 KB Output is correct
105 Correct 1650 ms 251776 KB Output is correct
106 Correct 2188 ms 253332 KB Output is correct
107 Correct 1810 ms 251680 KB Output is correct
108 Correct 1955 ms 251476 KB Output is correct