oj.uz

Submission #847851

# Submission time Handle Problem Language Result Execution time Memory
847851 2023-09-10T15:41:02 Z fanwen Two Currencies (JOI23_currencies) C++17
100 / 100
 2772 ms 256416 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;
        }
        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

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 2 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4600 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 9 ms 8792 KB Output is correct
6 Correct 13 ms 9304 KB Output is correct
7 Correct 11 ms 7516 KB Output is correct
8 Correct 14 ms 9428 KB Output is correct
9 Correct 13 ms 9304 KB Output is correct
10 Correct 14 ms 9304 KB Output is correct
11 Correct 14 ms 9304 KB Output is correct
12 Correct 13 ms 9428 KB Output is correct
13 Correct 7 ms 9560 KB Output is correct
14 Correct 8 ms 9304 KB Output is correct
15 Correct 9 ms 9304 KB Output is correct
16 Correct 11 ms 9308 KB Output is correct
17 Correct 10 ms 9304 KB Output is correct
18 Correct 9 ms 9308 KB Output is correct
19 Correct 8 ms 9304 KB Output is correct
20 Correct 8 ms 9304 KB Output is correct
21 Correct 8 ms 9304 KB Output is correct
22 Correct 8 ms 9304 KB Output is correct
23 Correct 13 ms 9304 KB Output is correct
24 Correct 14 ms 9304 KB Output is correct
25 Correct 13 ms 9428 KB Output is correct
26 Correct 12 ms 9304 KB Output is correct
27 Correct 11 ms 9308 KB Output is correct
28 Correct 12 ms 9308 KB Output is correct
29 Correct 9 ms 9304 KB Output is correct
30 Correct 14 ms 9304 KB Output is correct
31 Correct 14 ms 9304 KB Output is correct
32 Correct 14 ms 9304 KB Output is correct
33 Correct 7 ms 9560 KB Output is correct
34 Correct 6 ms 9564 KB Output is correct
35 Correct 7 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 18 ms 9304 KB Output is correct
3 Correct 15 ms 9308 KB Output is correct
4 Correct 15 ms 9308 KB Output is correct
5 Correct 1577 ms 246312 KB Output is correct
6 Correct 2077 ms 164180 KB Output is correct
7 Correct 2008 ms 201984 KB Output is correct
8 Correct 1419 ms 212704 KB Output is correct
9 Correct 1373 ms 211840 KB Output is correct
10 Correct 2646 ms 247176 KB Output is correct
11 Correct 2589 ms 246992 KB Output is correct
12 Correct 2511 ms 246760 KB Output is correct
13 Correct 2435 ms 246692 KB Output is correct
14 Correct 2314 ms 246688 KB Output is correct
15 Correct 1096 ms 255468 KB Output is correct
16 Correct 1014 ms 256180 KB Output is correct
17 Correct 1159 ms 255052 KB Output is correct
18 Correct 2257 ms 246884 KB Output is correct
19 Correct 2143 ms 246768 KB Output is correct
20 Correct 2311 ms 246864 KB Output is correct
21 Correct 667 ms 246904 KB Output is correct
22 Correct 627 ms 247180 KB Output is correct
23 Correct 686 ms 247036 KB Output is correct
24 Correct 693 ms 246932 KB Output is correct
25 Correct 1803 ms 246812 KB Output is correct
26 Correct 2015 ms 247044 KB Output is correct
27 Correct 1679 ms 246848 KB Output is correct
28 Correct 1788 ms 246816 KB Output is correct
29 Correct 1430 ms 246624 KB Output is correct
30 Correct 1927 ms 246936 KB Output is correct
31 Correct 1696 ms 246772 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 7 ms 9560 KB Output is correct
3 Correct 7 ms 9564 KB Output is correct
4 Correct 9 ms 9596 KB Output is correct
5 Correct 583 ms 245052 KB Output is correct
6 Correct 491 ms 236892 KB Output is correct
7 Correct 884 ms 140676 KB Output is correct
8 Correct 1111 ms 255940 KB Output is correct
9 Correct 1116 ms 256108 KB Output is correct
10 Correct 1154 ms 256380 KB Output is correct
11 Correct 854 ms 256284 KB Output is correct
12 Correct 815 ms 256172 KB Output is correct
13 Correct 845 ms 256120 KB Output is correct
14 Correct 553 ms 256416 KB Output is correct
15 Correct 496 ms 255948 KB Output is correct
16 Correct 633 ms 256344 KB Output is correct
17 Correct 643 ms 256304 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4600 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 9 ms 8792 KB Output is correct
6 Correct 13 ms 9304 KB Output is correct
7 Correct 11 ms 7516 KB Output is correct
8 Correct 14 ms 9428 KB Output is correct
9 Correct 13 ms 9304 KB Output is correct
10 Correct 14 ms 9304 KB Output is correct
11 Correct 14 ms 9304 KB Output is correct
12 Correct 13 ms 9428 KB Output is correct
13 Correct 7 ms 9560 KB Output is correct
14 Correct 8 ms 9304 KB Output is correct
15 Correct 9 ms 9304 KB Output is correct
16 Correct 11 ms 9308 KB Output is correct
17 Correct 10 ms 9304 KB Output is correct
18 Correct 9 ms 9308 KB Output is correct
19 Correct 8 ms 9304 KB Output is correct
20 Correct 8 ms 9304 KB Output is correct
21 Correct 8 ms 9304 KB Output is correct
22 Correct 8 ms 9304 KB Output is correct
23 Correct 13 ms 9304 KB Output is correct
24 Correct 14 ms 9304 KB Output is correct
25 Correct 13 ms 9428 KB Output is correct
26 Correct 12 ms 9304 KB Output is correct
27 Correct 11 ms 9308 KB Output is correct
28 Correct 12 ms 9308 KB Output is correct
29 Correct 9 ms 9304 KB Output is correct
30 Correct 14 ms 9304 KB Output is correct
31 Correct 14 ms 9304 KB Output is correct
32 Correct 14 ms 9304 KB Output is correct
33 Correct 7 ms 9560 KB Output is correct
34 Correct 6 ms 9564 KB Output is correct
35 Correct 7 ms 9560 KB Output is correct
36 Correct 1 ms 4440 KB Output is correct
37 Correct 18 ms 9304 KB Output is correct
38 Correct 15 ms 9308 KB Output is correct
39 Correct 15 ms 9308 KB Output is correct
40 Correct 1577 ms 246312 KB Output is correct
41 Correct 2077 ms 164180 KB Output is correct
42 Correct 2008 ms 201984 KB Output is correct
43 Correct 1419 ms 212704 KB Output is correct
44 Correct 1373 ms 211840 KB Output is correct
45 Correct 2646 ms 247176 KB Output is correct
46 Correct 2589 ms 246992 KB Output is correct
47 Correct 2511 ms 246760 KB Output is correct
48 Correct 2435 ms 246692 KB Output is correct
49 Correct 2314 ms 246688 KB Output is correct
50 Correct 1096 ms 255468 KB Output is correct
51 Correct 1014 ms 256180 KB Output is correct
52 Correct 1159 ms 255052 KB Output is correct
53 Correct 2257 ms 246884 KB Output is correct
54 Correct 2143 ms 246768 KB Output is correct
55 Correct 2311 ms 246864 KB Output is correct
56 Correct 667 ms 246904 KB Output is correct
57 Correct 627 ms 247180 KB Output is correct
58 Correct 686 ms 247036 KB Output is correct
59 Correct 693 ms 246932 KB Output is correct
60 Correct 1803 ms 246812 KB Output is correct
61 Correct 2015 ms 247044 KB Output is correct
62 Correct 1679 ms 246848 KB Output is correct
63 Correct 1788 ms 246816 KB Output is correct
64 Correct 1430 ms 246624 KB Output is correct
65 Correct 1927 ms 246936 KB Output is correct
66 Correct 1696 ms 246772 KB Output is correct
67 Correct 1 ms 4440 KB Output is correct
68 Correct 7 ms 9560 KB Output is correct
69 Correct 7 ms 9564 KB Output is correct
70 Correct 9 ms 9596 KB Output is correct
71 Correct 583 ms 245052 KB Output is correct
72 Correct 491 ms 236892 KB Output is correct
73 Correct 884 ms 140676 KB Output is correct
74 Correct 1111 ms 255940 KB Output is correct
75 Correct 1116 ms 256108 KB Output is correct
76 Correct 1154 ms 256380 KB Output is correct
77 Correct 854 ms 256284 KB Output is correct
78 Correct 815 ms 256172 KB Output is correct
79 Correct 845 ms 256120 KB Output is correct
80 Correct 553 ms 256416 KB Output is correct
81 Correct 496 ms 255948 KB Output is correct
82 Correct 633 ms 256344 KB Output is correct
83 Correct 643 ms 256304 KB Output is correct
84 Correct 1641 ms 205960 KB Output is correct
85 Correct 1643 ms 134092 KB Output is correct
86 Correct 1462 ms 131752 KB Output is correct
87 Correct 2728 ms 246880 KB Output is correct
88 Correct 2666 ms 246848 KB Output is correct
89 Correct 2712 ms 246608 KB Output is correct
90 Correct 2772 ms 246612 KB Output is correct
91 Correct 2728 ms 246556 KB Output is correct
92 Correct 1329 ms 252388 KB Output is correct
93 Correct 1202 ms 254732 KB Output is correct
94 Correct 2343 ms 247092 KB Output is correct
95 Correct 2561 ms 246984 KB Output is correct
96 Correct 2398 ms 246840 KB Output is correct
97 Correct 2464 ms 246896 KB Output is correct
98 Correct 1124 ms 246868 KB Output is correct
99 Correct 1077 ms 246984 KB Output is correct
100 Correct 1139 ms 246832 KB Output is correct
101 Correct 1211 ms 247028 KB Output is correct
102 Correct 2089 ms 246952 KB Output is correct
103 Correct 2077 ms 247004 KB Output is correct
104 Correct 2009 ms 246784 KB Output is correct
105 Correct 1476 ms 246920 KB Output is correct
106 Correct 1966 ms 246608 KB Output is correct
107 Correct 1537 ms 246416 KB Output is correct
108 Correct 1765 ms 246612 KB Output is correct