oj.uz

Submission #1031503

# Submission time Handle Problem Language Result Execution time Memory
1031503 2024-07-22T22:16:06 Z mdn2002 Tourism (JOI23_tourism) C++17
100 / 100
 847 ms 92760 KB 
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    FenwickTree bit(m + 1);
    vector<vector<int>> gr(n + 1);
    vector st(n + 1, vector<int> (20));
    vector<int> dp(n + 1), sum(n + 1);
    for (int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    function<void(int, int)> dfs = [&] (int x, int p) {
        st[x][0] = p;
        dp[x] = dp[p] + 1;
        sum[x] = 1;
        for (auto u : gr[x]) {
            if (u == p) continue;
            dfs(u, x);
            sum[x] += sum[u];
        }
    };
    dfs(1, 0);
    for (int j = 1; j <= 19; j ++) {
        for (int i = 1; i <= n; i ++) st[i][j] = st[st[i][j - 1]][j - 1];
    }
    function lca = [&] (int x, int y) {
        if (dp[x] > dp[y]) swap(x, y);
        int dif = dp[y] - dp[x], bt = 1;
        for (int i = 0; i < 20; i ++) {
            if ((dif & bt)) y = st[y][i];
            bt *= 2;
        }
        if (x == y) return x;
        for (int i = 19; i >= 0; i --) {
            if (st[x][i] != st[y][i]) {
                x = st[x][i];
                y = st[y][i];
            }
        }
        return st[x][0];
    };

    vector<int> c(m + 1), mx(n + 1), ans(q + 1);
    for (int i = 1; i <= m; i ++) cin >> c[i];
    vector qr(m + 1, vector<pair<int, int>>());
    for (int i = 0; i < q; i ++) {
        int l, r;
        cin >> l >> r;
        qr[r].push_back({l, i});
    }
    vector s(n + 1, set<pair<int, int>>());
    vector add(n + 1, vector<pair<int, int>>());
    vector del(n + 1, vector<int>());
    for (int r = 2; r <= m; r ++) {
        int x = c[r], y = c[r - 1], z = lca(x, y);
        add[x].push_back({r, 0});
        add[y].push_back({r, 1});
        del[z].push_back(r);
    }
    vector fuck(m + 1, vector<vector<pair<int, int>>>(2));
    function<void(int, int)> hld = [&] (int x, int p) {
        int mx = 0, bst = 0;
        for (auto u : gr[x]) {
            if (u == p) continue;
            if (mx < sum[u]) {
                mx = sum[u];
                bst = u;
            }
        }
        for (auto u : gr[x]) {
            if (u == p || u == bst) continue;
            hld(u, x);
        }
        if (bst) {
            hld(bst, x);
            swap(s[x], s[bst]);
        }
        for (auto z : add[x]) s[x].insert(z);
        for (auto u : gr[x]) {
            if (u == p || u == bst) continue;
            for (auto z : s[u]) s[x].insert(z);
        }
        //cout << ' ' << x << endl;
        //for (auto [a, b] : s[x]) cout << ' ' << a << ' ' << b << endl;
        for (auto u : gr[x]) {
            if (u == p || u == bst) continue;
            for (auto z : s[u]) {
                auto it_k = s[x].upper_bound(z);
                if (it_k == s[x].end()) continue;
                auto k = *it_k;
                if (z.first == k.first) continue;
                fuck[k.first][k.second].push_back({z.first, dp[x]});
            }
            for (auto z : s[u]) {
                auto it_k = s[x].lower_bound(z);
                if (it_k == s[x].begin()) continue;
                auto k = *--it_k;
                if (z.first == k.first) continue;
                fuck[z.first][z.second].push_back({k.first, dp[x]});
            }
            s[u].clear();
        }
        for (auto z : add[x]) {
            auto it_k = s[x].upper_bound(z);
            if (it_k == s[x].end()) continue;
            auto k = *it_k;
            if (z.first == k.first) continue;
            fuck[k.first][k.second].push_back({z.first, dp[x]});
        }
        for (auto z : add[x]) {
            auto it_k = s[x].lower_bound(z);
            if (it_k == s[x].begin()) continue;
            auto k = *--it_k;
            if (z.first == k.first) continue;
            fuck[z.first][z.second].push_back({k.first, dp[x]});
        }

        for (auto u : del[x]) {
            s[x].erase({u, 0});
            s[x].erase({u, 1});
        }

        for (auto zz : del[x]) {
            pair z = {zz, 0};
            auto it_k = s[x].upper_bound(z);
            if (it_k == s[x].end()) continue;
            auto k = *it_k;

            if (it_k == s[x].begin()) fuck[k.first][k.second].push_back({0, dp[x] - 1});
            else fuck[k.first][k.second].push_back({(*(--it_k)).first, dp[x] - 1});
        }
    };
    hld(1, 0);
    for (int r = 1; r <= m; r ++) {
        if (r != 1) {
            int x = c[r], y = c[r - 1], z = lca(x, y);
            if (x == z) bit.add(r, dp[y] - dp[x] + 1);
            else if (y == z) bit.add(r, dp[x] - dp[y] + 1);
            else bit.add(r, dp[x] + dp[y] - 2 * dp[z] + 1);
            fuck[r][0].push_back({0, dp[z] - 1});
            fuck[r][1].push_back({0, dp[z]});

            for (int i = 0; i < fuck[r][0].size() - 1; i ++) {
                auto [l, b] = fuck[r][0][i];
                auto [ll, bb] = fuck[r][0][i + 1];
                if (l) bit.add(l, -(b - bb));
            }
            for (int i = 0; i < fuck[r][1].size() - 1; i ++) {
                auto [l, b] = fuck[r][1][i];
                auto [ll, bb] = fuck[r][1][i + 1];
                if (l) bit.add(l, -(b - bb));
            }
        }
        for (auto [l, i] : qr[r]) {
            if (l == r) ans[i] = 1;
            else ans[i] = bit.sum(r) - bit.sum(l);
        }
    }

    for (int i = 0; i < q; i ++) cout << ans[i] << endl;
}
/*
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6
*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

Compilation message

tourism.cpp: In function 'void solve()':
tourism.cpp:172:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |             for (int i = 0; i < fuck[r][0].size() - 1; i ++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:177:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |             for (int i = 0; i < fuck[r][1].size() - 1; i ++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 668 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 672 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 668 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 672 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 1372 KB Output is correct
31 Correct 10 ms 1372 KB Output is correct
32 Correct 9 ms 1884 KB Output is correct
33 Correct 8 ms 1884 KB Output is correct
34 Correct 8 ms 1628 KB Output is correct
35 Correct 11 ms 1884 KB Output is correct
36 Correct 8 ms 1748 KB Output is correct
37 Correct 8 ms 1884 KB Output is correct
38 Correct 6 ms 1924 KB Output is correct
39 Correct 6 ms 1884 KB Output is correct
40 Correct 7 ms 1884 KB Output is correct
41 Correct 6 ms 1884 KB Output is correct
42 Correct 6 ms 1748 KB Output is correct
43 Correct 7 ms 1884 KB Output is correct
44 Correct 7 ms 1884 KB Output is correct
45 Correct 7 ms 1860 KB Output is correct
46 Correct 7 ms 1628 KB Output is correct
47 Correct 7 ms 1864 KB Output is correct
48 Correct 8 ms 1884 KB Output is correct
49 Correct 11 ms 1884 KB Output is correct
50 Correct 6 ms 1744 KB Output is correct
51 Correct 6 ms 1884 KB Output is correct
52 Correct 6 ms 1652 KB Output is correct
53 Correct 6 ms 1880 KB Output is correct
54 Correct 6 ms 1628 KB Output is correct
55 Correct 6 ms 1692 KB Output is correct
56 Correct 4 ms 860 KB Output is correct
57 Correct 3 ms 856 KB Output is correct
58 Correct 8 ms 1884 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 856 KB Output is correct
4 Correct 328 ms 51880 KB Output is correct
5 Correct 259 ms 55124 KB Output is correct
6 Correct 354 ms 66568 KB Output is correct
7 Correct 411 ms 76624 KB Output is correct
8 Correct 440 ms 76624 KB Output is correct
9 Correct 457 ms 76644 KB Output is correct
10 Correct 466 ms 76532 KB Output is correct
11 Correct 454 ms 76728 KB Output is correct
12 Correct 279 ms 74944 KB Output is correct
13 Correct 300 ms 75092 KB Output is correct
14 Correct 269 ms 75088 KB Output is correct
15 Correct 141 ms 48324 KB Output is correct
16 Correct 454 ms 76244 KB Output is correct
17 Correct 225 ms 30472 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 273 ms 41732 KB Output is correct
3 Correct 436 ms 58832 KB Output is correct
4 Correct 331 ms 50328 KB Output is correct
5 Correct 546 ms 78024 KB Output is correct
6 Correct 525 ms 75472 KB Output is correct
7 Correct 557 ms 74960 KB Output is correct
8 Correct 503 ms 75468 KB Output is correct
9 Correct 524 ms 76752 KB Output is correct
10 Correct 532 ms 76924 KB Output is correct
11 Correct 522 ms 76224 KB Output is correct
12 Correct 519 ms 75604 KB Output is correct
13 Correct 513 ms 76372 KB Output is correct
14 Correct 563 ms 77812 KB Output is correct
15 Correct 634 ms 82968 KB Output is correct
16 Correct 500 ms 74064 KB Output is correct
17 Correct 544 ms 75724 KB Output is correct
18 Correct 491 ms 75744 KB Output is correct
19 Correct 552 ms 69112 KB Output is correct
20 Correct 522 ms 68440 KB Output is correct
21 Correct 489 ms 69328 KB Output is correct
22 Correct 499 ms 69432 KB Output is correct
23 Correct 505 ms 68468 KB Output is correct
24 Correct 509 ms 68772 KB Output is correct
25 Correct 517 ms 68928 KB Output is correct
26 Correct 538 ms 68972 KB Output is correct
27 Correct 468 ms 69200 KB Output is correct
28 Correct 518 ms 68948 KB Output is correct
29 Correct 484 ms 69328 KB Output is correct
30 Correct 528 ms 69460 KB Output is correct
31 Correct 548 ms 69836 KB Output is correct
32 Correct 538 ms 70476 KB Output is correct
33 Correct 583 ms 73180 KB Output is correct
34 Correct 607 ms 73628 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 674 ms 71440 KB Output is correct
5 Correct 650 ms 73676 KB Output is correct
6 Correct 753 ms 86984 KB Output is correct
7 Correct 830 ms 92384 KB Output is correct
8 Correct 847 ms 92468 KB Output is correct
9 Correct 780 ms 92744 KB Output is correct
10 Correct 757 ms 92620 KB Output is correct
11 Correct 749 ms 92440 KB Output is correct
12 Correct 730 ms 92760 KB Output is correct
13 Correct 776 ms 92748 KB Output is correct
14 Correct 233 ms 30468 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 668 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 672 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 1372 KB Output is correct
31 Correct 10 ms 1372 KB Output is correct
32 Correct 9 ms 1884 KB Output is correct
33 Correct 8 ms 1884 KB Output is correct
34 Correct 8 ms 1628 KB Output is correct
35 Correct 11 ms 1884 KB Output is correct
36 Correct 8 ms 1748 KB Output is correct
37 Correct 8 ms 1884 KB Output is correct
38 Correct 6 ms 1924 KB Output is correct
39 Correct 6 ms 1884 KB Output is correct
40 Correct 7 ms 1884 KB Output is correct
41 Correct 6 ms 1884 KB Output is correct
42 Correct 6 ms 1748 KB Output is correct
43 Correct 7 ms 1884 KB Output is correct
44 Correct 7 ms 1884 KB Output is correct
45 Correct 7 ms 1860 KB Output is correct
46 Correct 7 ms 1628 KB Output is correct
47 Correct 7 ms 1864 KB Output is correct
48 Correct 8 ms 1884 KB Output is correct
49 Correct 11 ms 1884 KB Output is correct
50 Correct 6 ms 1744 KB Output is correct
51 Correct 6 ms 1884 KB Output is correct
52 Correct 6 ms 1652 KB Output is correct
53 Correct 6 ms 1880 KB Output is correct
54 Correct 6 ms 1628 KB Output is correct
55 Correct 6 ms 1692 KB Output is correct
56 Correct 4 ms 860 KB Output is correct
57 Correct 3 ms 856 KB Output is correct
58 Correct 8 ms 1884 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 4 ms 856 KB Output is correct
62 Correct 328 ms 51880 KB Output is correct
63 Correct 259 ms 55124 KB Output is correct
64 Correct 354 ms 66568 KB Output is correct
65 Correct 411 ms 76624 KB Output is correct
66 Correct 440 ms 76624 KB Output is correct
67 Correct 457 ms 76644 KB Output is correct
68 Correct 466 ms 76532 KB Output is correct
69 Correct 454 ms 76728 KB Output is correct
70 Correct 279 ms 74944 KB Output is correct
71 Correct 300 ms 75092 KB Output is correct
72 Correct 269 ms 75088 KB Output is correct
73 Correct 141 ms 48324 KB Output is correct
74 Correct 454 ms 76244 KB Output is correct
75 Correct 225 ms 30472 KB Output is correct
76 Correct 1 ms 344 KB Output is correct
77 Correct 273 ms 41732 KB Output is correct
78 Correct 436 ms 58832 KB Output is correct
79 Correct 331 ms 50328 KB Output is correct
80 Correct 546 ms 78024 KB Output is correct
81 Correct 525 ms 75472 KB Output is correct
82 Correct 557 ms 74960 KB Output is correct
83 Correct 503 ms 75468 KB Output is correct
84 Correct 524 ms 76752 KB Output is correct
85 Correct 532 ms 76924 KB Output is correct
86 Correct 522 ms 76224 KB Output is correct
87 Correct 519 ms 75604 KB Output is correct
88 Correct 513 ms 76372 KB Output is correct
89 Correct 563 ms 77812 KB Output is correct
90 Correct 634 ms 82968 KB Output is correct
91 Correct 500 ms 74064 KB Output is correct
92 Correct 544 ms 75724 KB Output is correct
93 Correct 491 ms 75744 KB Output is correct
94 Correct 552 ms 69112 KB Output is correct
95 Correct 522 ms 68440 KB Output is correct
96 Correct 489 ms 69328 KB Output is correct
97 Correct 499 ms 69432 KB Output is correct
98 Correct 505 ms 68468 KB Output is correct
99 Correct 509 ms 68772 KB Output is correct
100 Correct 517 ms 68928 KB Output is correct
101 Correct 538 ms 68972 KB Output is correct
102 Correct 468 ms 69200 KB Output is correct
103 Correct 518 ms 68948 KB Output is correct
104 Correct 484 ms 69328 KB Output is correct
105 Correct 528 ms 69460 KB Output is correct
106 Correct 548 ms 69836 KB Output is correct
107 Correct 538 ms 70476 KB Output is correct
108 Correct 583 ms 73180 KB Output is correct
109 Correct 607 ms 73628 KB Output is correct
110 Correct 0 ms 348 KB Output is correct
111 Correct 1 ms 348 KB Output is correct
112 Correct 4 ms 860 KB Output is correct
113 Correct 674 ms 71440 KB Output is correct
114 Correct 650 ms 73676 KB Output is correct
115 Correct 753 ms 86984 KB Output is correct
116 Correct 830 ms 92384 KB Output is correct
117 Correct 847 ms 92468 KB Output is correct
118 Correct 780 ms 92744 KB Output is correct
119 Correct 757 ms 92620 KB Output is correct
120 Correct 749 ms 92440 KB Output is correct
121 Correct 730 ms 92760 KB Output is correct
122 Correct 776 ms 92748 KB Output is correct
123 Correct 233 ms 30468 KB Output is correct
124 Correct 559 ms 72660 KB Output is correct
125 Correct 397 ms 59996 KB Output is correct
126 Correct 664 ms 82236 KB Output is correct
127 Correct 651 ms 83144 KB Output is correct
128 Correct 635 ms 81596 KB Output is correct
129 Correct 611 ms 80332 KB Output is correct
130 Correct 667 ms 79316 KB Output is correct
131 Correct 506 ms 75348 KB Output is correct
132 Correct 519 ms 76380 KB Output is correct
133 Correct 509 ms 72856 KB Output is correct
134 Correct 621 ms 72532 KB Output is correct
135 Correct 609 ms 73776 KB Output is correct
136 Correct 603 ms 72528 KB Output is correct
137 Correct 434 ms 72232 KB Output is correct
138 Correct 434 ms 72392 KB Output is correct
139 Correct 435 ms 72136 KB Output is correct
140 Correct 454 ms 72140 KB Output is correct
141 Correct 415 ms 72136 KB Output is correct
142 Correct 458 ms 72136 KB Output is correct
143 Correct 170 ms 31176 KB Output is correct
144 Correct 654 ms 79528 KB Output is correct