oj.uz

Submission #843547

# Submission time Handle Problem Language Result Execution time Memory
843547 2023-09-04T04:47:19 Z Quadrilateral Two Currencies (JOI23_currencies) C++17
100 / 100
 3515 ms 65820 KB 
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define MAXN 100010
using namespace std;

typedef long long ll;

int N, M, Q;
int parent[20][MAXN];
int depth[MAXN];
int in[MAXN], out[MAXN];
int max_height;
int dfs_ordering[MAXN];
vector<int> adj[MAXN];

typedef struct save_points {
    ll s, e, val;
    bool operator < (const save_points& right) {
        return val < right.val;
    }
} save_points;

typedef struct Query {
    ll s, t, x, y;
} Query;

vector<save_points> SP;
vector<Query> queries;
int l[MAXN], r[MAXN];
vector< pair<int, int> > roads;

void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); }

void input() {
    cin >> N >> M >> Q;
    roads.resize(N);
    for (int i = 1; i <= N - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        roads[i] = { min(a, b), max(a, b) };
    }
    for (int i = 1; i <= M; i++) {
        int a, b;
        cin >> a >> b;
        save_points tmp = { roads[a].first, roads[a].second, b };
        SP.push_back(tmp);
    }
    sort(SP.begin(), SP.end());
    queries.resize(Q);
    for (int i = 0; i < Q; i++)
        cin >> queries[i].s >> queries[i].t >> queries[i].x >> queries[i].y;
}

int Euler_tour_idx, ordering_idx;

void Euler_tour(int n, int dep) { // set in, out, depth, parent
    dfs_ordering[n] = ++ordering_idx;
    in[n] = ++Euler_tour_idx;
    depth[n] = dep;
    for (int i = 0; i < adj[n].size(); i++) {
        int next = adj[n][i];
        if (in[next]) continue;
        parent[0][next] = n;
        Euler_tour(next, dep + 1);
    }
    ++Euler_tour_idx;
    out[n] = Euler_tour_idx;
}

void set_parent() { // for faster lca
    int tmp = N, cnt = 0;
    while (tmp > 1) {
        tmp >>= 1;
        cnt++;
    }
    max_height = cnt;
    for (int k = 1; k <= max_height; k++)
        for (int i = 2; i <= N; i++)
            if (parent[k - 1][i])
                parent[k][i] = parent[k - 1][parent[k - 1][i]];
}

int LCA(int a, int b) { // returns lca of node a and b
    if (depth[a] != depth[b]) {
        if (depth[a] < depth[b]) swap(a, b); // a is deeper
        ll dif = depth[a] - depth[b];
        for (ll i = 0; dif > 0; i++) {
            if (dif & 1) a = parent[i][a];
            dif >>= 1;
        }
    }

    if (a != b) {
        for (int k = max_height; 0 <= k; k--) {
            if (parent[k][a] != 0 && parent[k][a] != parent[k][b]) {
                a = parent[k][a];
                b = parent[k][b];
            }
        }
        a = parent[0][a];
    }

    return a;
}

ll tree1[8 * MAXN], tree2[8 * MAXN], tree3[8 * MAXN];

void update(ll tree[], int n, int s, int e, int tgIdx, ll val) {
    if (s == e) {
        tree[n] += val;
        return;
    }
    int lch = n << 1, rch = lch | 1, m = s + e >> 1;
    if (tgIdx <= m) update(tree, lch, s, m, tgIdx, val);
    else update(tree, rch, m + 1, e, tgIdx, val);
    tree[n] = tree[lch] + tree[rch];
}

ll query(ll tree[], int n, int s, int e, int fs, int fe) {
    if (e < fs || fe < s) return 0;
    if (fs <= s && e <= fe) return tree[n];
    int lch = n << 1, rch = lch | 1, m = s + e >> 1;
    ll left = query(tree, lch, s, m, fs, fe);
    ll right = query(tree, rch, m + 1, e, fs, fe);
    return left + right;
}

void segclear(int s = 1, int e = Euler_tour_idx, int n = 1) {
    tree1[n] = tree3[n] = 0;
    if (s == e) return;
    int m = s + e >> 1;
    segclear(s, m, n << 1);
    segclear(m + 1, e, n << 1 | 1);
}

vector<int> g[MAXN];
int ans[MAXN];
int totSP[MAXN]{};
int cnts[MAXN]{};

void solve() {
    for (int i = 0; i < MAXN; i++)
        ans[i] = -1;
    Euler_tour(1, 0); // for setting in, out, par
    set_parent(); // for faster LCA(O(logN))
    for (int i = 0; i < Q; i++) { // set for PBS
        l[i] = -1;
        r[i] = M;
    }

    for (int i = 0; i < M; i++) {
        int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
        if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
        update(tree2, 1, 1, Euler_tour_idx, in[E], 1); // SP 추가
        update(tree2, 1, 1, Euler_tour_idx, out[E], -1);
    }

    for (int j = 0; j < Q; j++) {
        int tmp_lca = LCA(queries[j].s, queries[j].t);
        ll tmp = query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree2, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree2, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
        totSP[j] = tmp;
    }

    while (1) {
        for (int i = 0; i < MAXN; i++)
            g[i].clear();
        segclear();
        bool flag = 0;
        for (int i = 0; i < Q; i++) {
            if (l[i] + 1 == r[i]) continue;
            flag = 1; g[l[i] + r[i] >> 1].push_back(i);
        }
        if (!flag) break;

        for (int i = 0; i < M; i++) {
            ll S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
            if (in[E] <= in[S] && in[S] <= out[E]) swap(S, E);
            update(tree1, 1, 1, Euler_tour_idx, in[E], VAL); // SP (은화 가중치) 추가
            update(tree1, 1, 1, Euler_tour_idx, out[E], -VAL);
            update(tree3, 1, 1, Euler_tour_idx, in[E], 1); // SP (단순 개수) 추가
            update(tree3, 1, 1, Euler_tour_idx, out[E], -1);
            for (auto j : g[i]) {
                int tmp_lca = LCA(queries[j].s, queries[j].t);
                ll tmp = query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree1, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree1, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
                ll tmp3 = query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].s]) + query(tree3, 1, 1, Euler_tour_idx, 1, in[queries[j].t]) - 2 * query(tree3, 1, 1, Euler_tour_idx, 1, in[tmp_lca]);
                if (tmp <= queries[j].y) {
                    ans[j] = max((ll)ans[j], queries[j].x - totSP[j] + tmp3);
                    l[j] = i;
                }
                else r[j] = i;
            }
        }
    }
}

void output() {
    for (int i = 0; i < Q; i++) {
        if (ans[i] == -1 && queries[i].x >= totSP[i])
            ans[i] = queries[i].x - totSP[i];
        cout << ans[i] << '\n';
    }
}

int main() {
    fastIO();
    input();
    solve();
    output();
    return 0;
}

Compilation message

currencies.cpp: In function 'void Euler_tour(int, int)':
currencies.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < adj[n].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:118:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int lch = n << 1, rch = lch | 1, m = s + e >> 1;
      |                                          ~~^~~
currencies.cpp: In function 'll query(ll*, int, int, int, int, int)':
currencies.cpp:127:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int lch = n << 1, rch = lch | 1, m = s + e >> 1;
      |                                          ~~^~~
currencies.cpp: In function 'void segclear(int, int, int)':
currencies.cpp:136:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |     int m = s + e >> 1;
      |             ~~^~~
currencies.cpp: In function 'void solve()':
currencies.cpp:157:39: warning: unused variable 'VAL' [-Wunused-variable]
  157 |         int S = SP[i].s, E = SP[i].e, VAL = SP[i].val;
      |                                       ^~~
currencies.cpp:176:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |             flag = 1; g[l[i] + r[i] >> 1].push_back(i);
      |                         ~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14828 KB Output is correct
5 Correct 17 ms 19036 KB Output is correct
6 Correct 21 ms 17244 KB Output is correct
7 Correct 19 ms 17240 KB Output is correct
8 Correct 23 ms 17496 KB Output is correct
9 Correct 23 ms 17240 KB Output is correct
10 Correct 24 ms 17244 KB Output is correct
11 Correct 23 ms 17240 KB Output is correct
12 Correct 23 ms 17244 KB Output is correct
13 Correct 24 ms 17464 KB Output is correct
14 Correct 25 ms 17244 KB Output is correct
15 Correct 30 ms 17744 KB Output is correct
16 Correct 24 ms 17244 KB Output is correct
17 Correct 26 ms 17244 KB Output is correct
18 Correct 25 ms 17244 KB Output is correct
19 Correct 21 ms 15288 KB Output is correct
20 Correct 21 ms 15192 KB Output is correct
21 Correct 21 ms 15192 KB Output is correct
22 Correct 24 ms 15196 KB Output is correct
23 Correct 18 ms 17240 KB Output is correct
24 Correct 23 ms 17500 KB Output is correct
25 Correct 19 ms 17244 KB Output is correct
26 Correct 16 ms 17316 KB Output is correct
27 Correct 16 ms 19292 KB Output is correct
28 Correct 16 ms 17144 KB Output is correct
29 Correct 17 ms 17240 KB Output is correct
30 Correct 25 ms 17372 KB Output is correct
31 Correct 23 ms 17296 KB Output is correct
32 Correct 23 ms 17244 KB Output is correct
33 Correct 24 ms 19288 KB Output is correct
34 Correct 25 ms 17412 KB Output is correct
35 Correct 24 ms 17440 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 23 ms 17288 KB Output is correct
3 Correct 23 ms 17324 KB Output is correct
4 Correct 23 ms 17244 KB Output is correct
5 Correct 1912 ms 49448 KB Output is correct
6 Correct 2036 ms 52796 KB Output is correct
7 Correct 2065 ms 52928 KB Output is correct
8 Correct 1533 ms 47672 KB Output is correct
9 Correct 1555 ms 48984 KB Output is correct
10 Correct 2676 ms 55476 KB Output is correct
11 Correct 2802 ms 55592 KB Output is correct
12 Correct 2778 ms 55516 KB Output is correct
13 Correct 2662 ms 55420 KB Output is correct
14 Correct 2598 ms 55504 KB Output is correct
15 Correct 3330 ms 64876 KB Output is correct
16 Correct 3476 ms 65732 KB Output is correct
17 Correct 3409 ms 64396 KB Output is correct
18 Correct 2995 ms 57928 KB Output is correct
19 Correct 3266 ms 57788 KB Output is correct
20 Correct 3261 ms 58744 KB Output is correct
21 Correct 2409 ms 54080 KB Output is correct
22 Correct 2387 ms 53612 KB Output is correct
23 Correct 2336 ms 54032 KB Output is correct
24 Correct 2494 ms 53588 KB Output is correct
25 Correct 2029 ms 56708 KB Output is correct
26 Correct 2056 ms 55880 KB Output is correct
27 Correct 1874 ms 56048 KB Output is correct
28 Correct 1405 ms 54420 KB Output is correct
29 Correct 1426 ms 53184 KB Output is correct
30 Correct 1612 ms 53692 KB Output is correct
31 Correct 1695 ms 53828 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 25 ms 19384 KB Output is correct
3 Correct 24 ms 17496 KB Output is correct
4 Correct 24 ms 17500 KB Output is correct
5 Correct 1861 ms 57240 KB Output is correct
6 Correct 1801 ms 56660 KB Output is correct
7 Correct 2194 ms 51544 KB Output is correct
8 Correct 3171 ms 65092 KB Output is correct
9 Correct 3046 ms 65356 KB Output is correct
10 Correct 3187 ms 65820 KB Output is correct
11 Correct 2005 ms 65240 KB Output is correct
12 Correct 2025 ms 65208 KB Output is correct
13 Correct 2021 ms 65556 KB Output is correct
14 Correct 1468 ms 64220 KB Output is correct
15 Correct 1551 ms 64224 KB Output is correct
16 Correct 1727 ms 64620 KB Output is correct
17 Correct 1864 ms 64520 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14828 KB Output is correct
5 Correct 17 ms 19036 KB Output is correct
6 Correct 21 ms 17244 KB Output is correct
7 Correct 19 ms 17240 KB Output is correct
8 Correct 23 ms 17496 KB Output is correct
9 Correct 23 ms 17240 KB Output is correct
10 Correct 24 ms 17244 KB Output is correct
11 Correct 23 ms 17240 KB Output is correct
12 Correct 23 ms 17244 KB Output is correct
13 Correct 24 ms 17464 KB Output is correct
14 Correct 25 ms 17244 KB Output is correct
15 Correct 30 ms 17744 KB Output is correct
16 Correct 24 ms 17244 KB Output is correct
17 Correct 26 ms 17244 KB Output is correct
18 Correct 25 ms 17244 KB Output is correct
19 Correct 21 ms 15288 KB Output is correct
20 Correct 21 ms 15192 KB Output is correct
21 Correct 21 ms 15192 KB Output is correct
22 Correct 24 ms 15196 KB Output is correct
23 Correct 18 ms 17240 KB Output is correct
24 Correct 23 ms 17500 KB Output is correct
25 Correct 19 ms 17244 KB Output is correct
26 Correct 16 ms 17316 KB Output is correct
27 Correct 16 ms 19292 KB Output is correct
28 Correct 16 ms 17144 KB Output is correct
29 Correct 17 ms 17240 KB Output is correct
30 Correct 25 ms 17372 KB Output is correct
31 Correct 23 ms 17296 KB Output is correct
32 Correct 23 ms 17244 KB Output is correct
33 Correct 24 ms 19288 KB Output is correct
34 Correct 25 ms 17412 KB Output is correct
35 Correct 24 ms 17440 KB Output is correct
36 Correct 3 ms 14680 KB Output is correct
37 Correct 23 ms 17288 KB Output is correct
38 Correct 23 ms 17324 KB Output is correct
39 Correct 23 ms 17244 KB Output is correct
40 Correct 1912 ms 49448 KB Output is correct
41 Correct 2036 ms 52796 KB Output is correct
42 Correct 2065 ms 52928 KB Output is correct
43 Correct 1533 ms 47672 KB Output is correct
44 Correct 1555 ms 48984 KB Output is correct
45 Correct 2676 ms 55476 KB Output is correct
46 Correct 2802 ms 55592 KB Output is correct
47 Correct 2778 ms 55516 KB Output is correct
48 Correct 2662 ms 55420 KB Output is correct
49 Correct 2598 ms 55504 KB Output is correct
50 Correct 3330 ms 64876 KB Output is correct
51 Correct 3476 ms 65732 KB Output is correct
52 Correct 3409 ms 64396 KB Output is correct
53 Correct 2995 ms 57928 KB Output is correct
54 Correct 3266 ms 57788 KB Output is correct
55 Correct 3261 ms 58744 KB Output is correct
56 Correct 2409 ms 54080 KB Output is correct
57 Correct 2387 ms 53612 KB Output is correct
58 Correct 2336 ms 54032 KB Output is correct
59 Correct 2494 ms 53588 KB Output is correct
60 Correct 2029 ms 56708 KB Output is correct
61 Correct 2056 ms 55880 KB Output is correct
62 Correct 1874 ms 56048 KB Output is correct
63 Correct 1405 ms 54420 KB Output is correct
64 Correct 1426 ms 53184 KB Output is correct
65 Correct 1612 ms 53692 KB Output is correct
66 Correct 1695 ms 53828 KB Output is correct
67 Correct 3 ms 14684 KB Output is correct
68 Correct 25 ms 19384 KB Output is correct
69 Correct 24 ms 17496 KB Output is correct
70 Correct 24 ms 17500 KB Output is correct
71 Correct 1861 ms 57240 KB Output is correct
72 Correct 1801 ms 56660 KB Output is correct
73 Correct 2194 ms 51544 KB Output is correct
74 Correct 3171 ms 65092 KB Output is correct
75 Correct 3046 ms 65356 KB Output is correct
76 Correct 3187 ms 65820 KB Output is correct
77 Correct 2005 ms 65240 KB Output is correct
78 Correct 2025 ms 65208 KB Output is correct
79 Correct 2021 ms 65556 KB Output is correct
80 Correct 1468 ms 64220 KB Output is correct
81 Correct 1551 ms 64224 KB Output is correct
82 Correct 1727 ms 64620 KB Output is correct
83 Correct 1864 ms 64520 KB Output is correct
84 Correct 1901 ms 49792 KB Output is correct
85 Correct 1715 ms 42932 KB Output is correct
86 Correct 1498 ms 42216 KB Output is correct
87 Correct 2657 ms 56196 KB Output is correct
88 Correct 2708 ms 55400 KB Output is correct
89 Correct 2751 ms 55276 KB Output is correct
90 Correct 2647 ms 55880 KB Output is correct
91 Correct 2918 ms 55432 KB Output is correct
92 Correct 3515 ms 63064 KB Output is correct
93 Correct 3378 ms 64148 KB Output is correct
94 Correct 3077 ms 57956 KB Output is correct
95 Correct 3048 ms 58192 KB Output is correct
96 Correct 3075 ms 57864 KB Output is correct
97 Correct 3152 ms 58408 KB Output is correct
98 Correct 2507 ms 53612 KB Output is correct
99 Correct 2351 ms 54060 KB Output is correct
100 Correct 2512 ms 54148 KB Output is correct
101 Correct 2335 ms 53508 KB Output is correct
102 Correct 1911 ms 55932 KB Output is correct
103 Correct 2005 ms 56248 KB Output is correct
104 Correct 1997 ms 56092 KB Output is correct
105 Correct 1462 ms 53392 KB Output is correct
106 Correct 1393 ms 54904 KB Output is correct
107 Correct 1663 ms 53284 KB Output is correct
108 Correct 1651 ms 53604 KB Output is correct