oj.uz

Submission #859703

# Submission time Handle Problem Language Result Execution time Memory
859703 2023-10-10T13:42:50 Z vjudge1 Two Currencies (JOI23_currencies) C++17
100 / 100
 3561 ms 62420 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "hihi"
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;  
int n, m, q, par[18][N], h[N], c[N], num[N], tail[N], lo[N], hi[N], bit1[N], bit2[N], ans[N], timedfs = 0;
vector<pii> edges(N + 5);
vector<int> adj[N];
vector<int> pos[N];
array<int, 4> a[N];
pii b[N];
void dfs(int i, int pre){
    num[i] = ++timedfs;
    for(int x : adj[i]){
        if(x == pre) continue;
        h[x] = h[i] + 1;
        par[0][x] = i;
        for(int j = 1; j < 18; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
    tail[i] = timedfs;
}
void upd(int bit[], int x, int val){
    for(; x <= n; x += x & -x){
        bit[x] += val;
    }
}
void upd(int bit[], int l, int r, int val){
    upd(bit, l, val);
    upd(bit, r + 1, -val);
}
int query(int bit[], int x){
    int res = 0;
    for(; x; x -= x & -x){
        res += bit[x];
    }
    return res;
}
int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int dist = h[x] - h[y];
    for(int i = 0; i < 18; i++){
        if(dist & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = 17; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}
int get(int bit[], int x, int y){
    if(h[x] > h[y]) swap(x, y);
    int u = lca(x, y);
    if(x == u){
        return query(bit, num[y]) - query(bit, num[x]);
    } else{
        return query(bit, num[x]) + query(bit, num[y]) - 2 * query(bit, num[u]);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1, x, y; i < n; i++){
        cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
        edges[i] = {x, y};
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        if(h[edges[i].first] > h[edges[i].second]) swap(edges[i].first, edges[i].second);
    }
    for(int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        b[i] = {edges[x].second, y};
    }
    sort(b + 1, b + m + 1, [](pii x, pii y){return x.second < y.second;});

    for(int i = 1; i <= q; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        // start end gold silver
        lo[i] = 1, hi[i] = m, ans[i] = -1;
    }
    for(int i = 1; i <= m; i++){
        upd(bit2, num[b[i].first], tail[b[i].first], 1);
    }
    for(int i = 1; i <= q; i++){
        int cur2 = get(bit2, a[i][0], a[i][1]);
        if(cur2 <= a[i][2]) ans[i] = a[i][2] - cur2;
    }
    for(int i = 1; i <= m; i++){
        upd(bit2, num[b[i].first], tail[b[i].first], -1);
    }
    // cout << endl;
    // for(int i = 1; i <= m; i++){
    //     cout << b[i].first << " " << b[i].second << endl;
    // }
    // cout << endl;

    for(int phase = 0; phase < 18; phase++){
        for(int j = 1; j <= m; j++){
            pos[j].clear();       
        }
        for(int j = 1; j <= q; j++){
            if(lo[j] > hi[j]) continue;
            int mid = (lo[j] + hi[j]) / 2;
            pos[mid].pb(j);
        }
        for(int i = 1; i <= m; i++){
            upd(bit2, num[b[i].first], tail[b[i].first], 1);
        }
        for(int i = 1; i <= m; i++){
            upd(bit1, num[b[i].first], tail[b[i].first], b[i].second);
            upd(bit2, num[b[i].first], tail[b[i].first], -1);
            for(int x : pos[i]){
                int cur = get(bit1, a[x][0], a[x][1]), cur2 = get(bit2, a[x][0], a[x][1]);
                // cout << i << " " << x << " " << a[x][0] << " " << a[x][1] << " " << cur << endl;
                if(cur <= a[x][3]){
                    lo[x] = i + 1;
                    if(cur2 <= a[x][2]) ans[x] = a[x][2] - cur2;
                } else{
                    hi[x] = i - 1;
                }
            }
        }
        for(int i = 0; i <= n; i++){
            bit1[i] = bit2[i] = 0;
        }
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26456 KB Output is correct
2 Correct 4 ms 26460 KB Output is correct
3 Correct 4 ms 26460 KB Output is correct
4 Correct 5 ms 26460 KB Output is correct
5 Correct 11 ms 27228 KB Output is correct
6 Correct 13 ms 26972 KB Output is correct
7 Correct 12 ms 26968 KB Output is correct
8 Correct 14 ms 26972 KB Output is correct
9 Correct 14 ms 26972 KB Output is correct
10 Correct 16 ms 26972 KB Output is correct
11 Correct 13 ms 26968 KB Output is correct
12 Correct 13 ms 26972 KB Output is correct
13 Correct 12 ms 27224 KB Output is correct
14 Correct 12 ms 27228 KB Output is correct
15 Correct 13 ms 27228 KB Output is correct
16 Correct 15 ms 27228 KB Output is correct
17 Correct 13 ms 26972 KB Output is correct
18 Correct 13 ms 27228 KB Output is correct
19 Correct 15 ms 26972 KB Output is correct
20 Correct 12 ms 26972 KB Output is correct
21 Correct 13 ms 27164 KB Output is correct
22 Correct 12 ms 26972 KB Output is correct
23 Correct 11 ms 27224 KB Output is correct
24 Correct 12 ms 26972 KB Output is correct
25 Correct 15 ms 26972 KB Output is correct
26 Correct 10 ms 26972 KB Output is correct
27 Correct 11 ms 26944 KB Output is correct
28 Correct 12 ms 26968 KB Output is correct
29 Correct 12 ms 26968 KB Output is correct
30 Correct 13 ms 27208 KB Output is correct
31 Correct 13 ms 26972 KB Output is correct
32 Correct 18 ms 27160 KB Output is correct
33 Correct 11 ms 27224 KB Output is correct
34 Correct 13 ms 27228 KB Output is correct
35 Correct 11 ms 27180 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26456 KB Output is correct
2 Correct 13 ms 26972 KB Output is correct
3 Correct 13 ms 26984 KB Output is correct
4 Correct 16 ms 27224 KB Output is correct
5 Correct 2224 ms 48836 KB Output is correct
6 Correct 1165 ms 53200 KB Output is correct
7 Correct 1843 ms 52144 KB Output is correct
8 Correct 1611 ms 48012 KB Output is correct
9 Correct 2268 ms 47376 KB Output is correct
10 Correct 2461 ms 56792 KB Output is correct
11 Correct 3025 ms 56464 KB Output is correct
12 Correct 3063 ms 56784 KB Output is correct
13 Correct 3420 ms 56348 KB Output is correct
14 Correct 2688 ms 56732 KB Output is correct
15 Correct 1883 ms 62112 KB Output is correct
16 Correct 2025 ms 62420 KB Output is correct
17 Correct 1995 ms 61632 KB Output is correct
18 Correct 2963 ms 56588 KB Output is correct
19 Correct 3070 ms 56368 KB Output is correct
20 Correct 3180 ms 56548 KB Output is correct
21 Correct 3561 ms 56916 KB Output is correct
22 Correct 3191 ms 56892 KB Output is correct
23 Correct 3274 ms 56856 KB Output is correct
24 Correct 3236 ms 56784 KB Output is correct
25 Correct 1945 ms 53748 KB Output is correct
26 Correct 2487 ms 52988 KB Output is correct
27 Correct 1136 ms 54240 KB Output is correct
28 Correct 494 ms 52756 KB Output is correct
29 Correct 552 ms 51400 KB Output is correct
30 Correct 1022 ms 51204 KB Output is correct
31 Correct 1048 ms 51148 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 11 ms 27016 KB Output is correct
3 Correct 11 ms 26972 KB Output is correct
4 Correct 11 ms 27056 KB Output is correct
5 Correct 998 ms 52172 KB Output is correct
6 Correct 875 ms 51660 KB Output is correct
7 Correct 635 ms 50328 KB Output is correct
8 Correct 1430 ms 59576 KB Output is correct
9 Correct 1446 ms 59276 KB Output is correct
10 Correct 1366 ms 59588 KB Output is correct
11 Correct 689 ms 59444 KB Output is correct
12 Correct 775 ms 59472 KB Output is correct
13 Correct 786 ms 59416 KB Output is correct
14 Correct 344 ms 59444 KB Output is correct
15 Correct 397 ms 59336 KB Output is correct
16 Correct 649 ms 59444 KB Output is correct
17 Correct 577 ms 59664 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26456 KB Output is correct
2 Correct 4 ms 26460 KB Output is correct
3 Correct 4 ms 26460 KB Output is correct
4 Correct 5 ms 26460 KB Output is correct
5 Correct 11 ms 27228 KB Output is correct
6 Correct 13 ms 26972 KB Output is correct
7 Correct 12 ms 26968 KB Output is correct
8 Correct 14 ms 26972 KB Output is correct
9 Correct 14 ms 26972 KB Output is correct
10 Correct 16 ms 26972 KB Output is correct
11 Correct 13 ms 26968 KB Output is correct
12 Correct 13 ms 26972 KB Output is correct
13 Correct 12 ms 27224 KB Output is correct
14 Correct 12 ms 27228 KB Output is correct
15 Correct 13 ms 27228 KB Output is correct
16 Correct 15 ms 27228 KB Output is correct
17 Correct 13 ms 26972 KB Output is correct
18 Correct 13 ms 27228 KB Output is correct
19 Correct 15 ms 26972 KB Output is correct
20 Correct 12 ms 26972 KB Output is correct
21 Correct 13 ms 27164 KB Output is correct
22 Correct 12 ms 26972 KB Output is correct
23 Correct 11 ms 27224 KB Output is correct
24 Correct 12 ms 26972 KB Output is correct
25 Correct 15 ms 26972 KB Output is correct
26 Correct 10 ms 26972 KB Output is correct
27 Correct 11 ms 26944 KB Output is correct
28 Correct 12 ms 26968 KB Output is correct
29 Correct 12 ms 26968 KB Output is correct
30 Correct 13 ms 27208 KB Output is correct
31 Correct 13 ms 26972 KB Output is correct
32 Correct 18 ms 27160 KB Output is correct
33 Correct 11 ms 27224 KB Output is correct
34 Correct 13 ms 27228 KB Output is correct
35 Correct 11 ms 27180 KB Output is correct
36 Correct 4 ms 26456 KB Output is correct
37 Correct 13 ms 26972 KB Output is correct
38 Correct 13 ms 26984 KB Output is correct
39 Correct 16 ms 27224 KB Output is correct
40 Correct 2224 ms 48836 KB Output is correct
41 Correct 1165 ms 53200 KB Output is correct
42 Correct 1843 ms 52144 KB Output is correct
43 Correct 1611 ms 48012 KB Output is correct
44 Correct 2268 ms 47376 KB Output is correct
45 Correct 2461 ms 56792 KB Output is correct
46 Correct 3025 ms 56464 KB Output is correct
47 Correct 3063 ms 56784 KB Output is correct
48 Correct 3420 ms 56348 KB Output is correct
49 Correct 2688 ms 56732 KB Output is correct
50 Correct 1883 ms 62112 KB Output is correct
51 Correct 2025 ms 62420 KB Output is correct
52 Correct 1995 ms 61632 KB Output is correct
53 Correct 2963 ms 56588 KB Output is correct
54 Correct 3070 ms 56368 KB Output is correct
55 Correct 3180 ms 56548 KB Output is correct
56 Correct 3561 ms 56916 KB Output is correct
57 Correct 3191 ms 56892 KB Output is correct
58 Correct 3274 ms 56856 KB Output is correct
59 Correct 3236 ms 56784 KB Output is correct
60 Correct 1945 ms 53748 KB Output is correct
61 Correct 2487 ms 52988 KB Output is correct
62 Correct 1136 ms 54240 KB Output is correct
63 Correct 494 ms 52756 KB Output is correct
64 Correct 552 ms 51400 KB Output is correct
65 Correct 1022 ms 51204 KB Output is correct
66 Correct 1048 ms 51148 KB Output is correct
67 Correct 4 ms 26460 KB Output is correct
68 Correct 11 ms 27016 KB Output is correct
69 Correct 11 ms 26972 KB Output is correct
70 Correct 11 ms 27056 KB Output is correct
71 Correct 998 ms 52172 KB Output is correct
72 Correct 875 ms 51660 KB Output is correct
73 Correct 635 ms 50328 KB Output is correct
74 Correct 1430 ms 59576 KB Output is correct
75 Correct 1446 ms 59276 KB Output is correct
76 Correct 1366 ms 59588 KB Output is correct
77 Correct 689 ms 59444 KB Output is correct
78 Correct 775 ms 59472 KB Output is correct
79 Correct 786 ms 59416 KB Output is correct
80 Correct 344 ms 59444 KB Output is correct
81 Correct 397 ms 59336 KB Output is correct
82 Correct 649 ms 59444 KB Output is correct
83 Correct 577 ms 59664 KB Output is correct
84 Correct 2132 ms 45596 KB Output is correct
85 Correct 1588 ms 45476 KB Output is correct
86 Correct 939 ms 45208 KB Output is correct
87 Correct 2552 ms 54056 KB Output is correct
88 Correct 2469 ms 53932 KB Output is correct
89 Correct 2490 ms 53724 KB Output is correct
90 Correct 2418 ms 53760 KB Output is correct
91 Correct 2500 ms 53712 KB Output is correct
92 Correct 1804 ms 57304 KB Output is correct
93 Correct 1613 ms 58616 KB Output is correct
94 Correct 2358 ms 53296 KB Output is correct
95 Correct 2379 ms 53524 KB Output is correct
96 Correct 2256 ms 53192 KB Output is correct
97 Correct 2410 ms 53472 KB Output is correct
98 Correct 2452 ms 54532 KB Output is correct
99 Correct 2348 ms 54220 KB Output is correct
100 Correct 3126 ms 54328 KB Output is correct
101 Correct 3186 ms 54540 KB Output is correct
102 Correct 1494 ms 53820 KB Output is correct
103 Correct 1910 ms 53808 KB Output is correct
104 Correct 1863 ms 53888 KB Output is correct
105 Correct 507 ms 50880 KB Output is correct
106 Correct 527 ms 52612 KB Output is correct
107 Correct 881 ms 50700 KB Output is correct
108 Correct 880 ms 51152 KB Output is correct