oj.uz

Submission #950883

# Submission time Handle Problem Language Result Execution time Memory
950883 2024-03-20T21:58:59 Z vjudge1 Tourism (JOI23_tourism) C++17
10 / 100
 5000 ms 43340 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AINT {
    int n;
    vi V;

    AINT(int N) : n(N), V(N, 1e9) {}
    
    void init() {

    }

    void update(int l, int r, int v, int u, int s, int d) {
        for(int i = l; i <= r; ++i) V[i] = v;
    }

    void update(int l, int r, int v) { update(l, r, v, 1, 0, n - 1); } /// l...r <- v

    int query(int r) {
        int cnt = 0;
        for(auto it : V)
            if(it <= r) ++cnt;
        return cnt;
    }
};

struct tree {
    int n, tmr = 0;
    vi par, niv, sz, nxt, in;
    vector<vi> L, G, Anc;

    AINT A;

    tree(int N) : n(N), par(N), niv(N), sz(N, 0), 
    nxt(N, 0), in(N, 0), L(N), G(N), A(N) {} /// nxt[u] e capul la lant

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        function<void(int, int, int)> dfs0 = [&](int u, int p, int li) {
            par[u] = p;
            niv[u] = li;
            sz[u] = 1;
            for (auto it : L[u])
                if (it != p) {
                    dfs0(it, u, li + 1);
                    sz[u] += it;
                    G[u].push_back(it);
                }
        };
        dfs0(0, -1, 0);

        A.init();

        function<void(int, int)> dfs1 = [&](int u, int p) {
            sort(all(G[u]), [&](auto a, auto b) { return sz[a] > sz[b]; });
            in[u] = tmr++;
            if (G[u].empty()) return;
            nxt[G[u][0]] = nxt[u];
            dfs1(G[u][0], u);
            for (int i = 1; i < G[u].size(); ++i) {
                nxt[G[u][i]] = G[u][i];
                dfs1(G[u][i], u);
            }
        };
        dfs1(0, -1);
        
        Anc.push_back(par);
        for (int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(vi(n, -1));
            for (int i = 0; i < n; ++i) {
                Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]];
            }
        }
    }

    int lift(int u, int nr) {
        for (int i = 0; i < (int)Anc.size(); ++i)
            if (nr & (1 << i))
                u = Anc[i][u];
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int i = (int)Anc.size() - 1; i >= 0; --i)
            if(Anc[i][u] != Anc[i][v]) {
                u = Anc[i][u];
                v = Anc[i][v];
            }
        return par[u];
    }

    void update_lant(int l, int u, int val) { /// (l, u] update
        if(niv[l] == niv[u]) return;
        while(u != -1) {
            if(niv[nxt[u]] > niv[l]) {
                A.update(in[nxt[u]], in[u], val);
                u = par[nxt[u]];
            } else {
                A.update(in[l] + 1, in[u], val);
                break;
            }
        }
    }

    void update(int u, int v, int val) {
        int l = lca(u, v);
        update_lant(l, u, val);
        update_lant(l, v, val);
    }

    int query(int r) { /// nr chestii <= r
        return A.query(r);
    }
};

struct RMQ_LCA {
    int m;
    tree &T;
    vi C;
    vector<vi> Re;

    RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
        Re.push_back(C);
        for(int k = 1; (1 << k) <= m; ++k) {
            Re.push_back(vi(m, 0));
            for(int i = 0; i < m; ++i) {
                if(i + (1 << (k - 1)) < m)
                    Re[k][i] = T.lca(Re[k - 1][i], Re[k - 1][i + (1 << (k - 1))]);
                else Re[k][i] = Re[k - 1][i];
            }
        }
    }

    int query(int st, int dr) {
        int l = 31 - __builtin_clz(dr - st + 1);
        return T.lca(Re[l][st], Re[l][dr - (1 << l) + 1]);
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    tree T(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        T.add_edge(u, v);
    }
    T.init();
    vi C(m);
    for(int i = 0; i < m; ++i) {
        cin >> C[i];
        --C[i];
    }

    RMQ_LCA Stramos(n, C, T);

    int rad = (int)round(sqrt(double(n)));
    vector<pair<ii, int> > Q;
    vi Re(q, 0);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        Q.push_back({ii{l, r}, i});
    }
    sort(all(Q));

    int ult = C.back();
    int p = int(Q.size()) - 1;
    for(int i = m - 1; i >= 0; --i) {
        T.update(ult, C[i], i + 1);
        ult = C[i];
        while(p >= 0 && Q[p].first.first == i) {
            auto [seg, id] = Q[p];
            auto [l, r] = seg;
            Re[id] = T.query(r);
            --p;
        }
    }

    for(auto it : Re)
        cout << it + 1 << "\n";
    return 0;
}

Compilation message

tourism.cpp: In lambda function:
tourism.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 1; i < G[u].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~
tourism.cpp: In constructor 'RMQ_LCA::RMQ_LCA(int, vi, tree&)':
tourism.cpp:140:8: warning: 'RMQ_LCA::C' will be initialized after [-Wreorder]
  140 |     vi C;
      |        ^
tourism.cpp:139:11: warning:   'tree& RMQ_LCA::T' [-Wreorder]
  139 |     tree &T;
      |           ^
tourism.cpp:143:5: warning:   when initialized here [-Wreorder]
  143 |     RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
      |     ^~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:182:9: warning: unused variable 'rad' [-Wunused-variable]
  182 |     int rad = (int)round(sqrt(double(n)));
      |         ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 3 ms 604 KB Output is correct
31 Correct 4 ms 604 KB Output is correct
32 Correct 5 ms 860 KB Output is correct
33 Correct 5 ms 852 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 5 ms 856 KB Output is correct
36 Correct 5 ms 860 KB Output is correct
37 Correct 5 ms 856 KB Output is correct
38 Correct 6 ms 1116 KB Output is correct
39 Correct 5 ms 1116 KB Output is correct
40 Correct 5 ms 1116 KB Output is correct
41 Correct 5 ms 1160 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 5 ms 1092 KB Output is correct
44 Correct 5 ms 860 KB Output is correct
45 Correct 5 ms 860 KB Output is correct
46 Correct 5 ms 860 KB Output is correct
47 Correct 5 ms 856 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 6 ms 856 KB Output is correct
50 Correct 4 ms 860 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 4 ms 860 KB Output is correct
54 Correct 5 ms 856 KB Output is correct
55 Correct 4 ms 860 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 4 ms 836 KB Output is correct
58 Correct 5 ms 860 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3315 ms 26240 KB Output is correct
5 Correct 4074 ms 33348 KB Output is correct
6 Correct 4122 ms 38704 KB Output is correct
7 Execution timed out 5052 ms 43340 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 127 ms 14396 KB Output is correct
3 Correct 165 ms 18260 KB Output is correct
4 Correct 188 ms 18516 KB Output is correct
5 Correct 136 ms 26704 KB Output is correct
6 Correct 135 ms 26720 KB Output is correct
7 Correct 131 ms 26708 KB Output is correct
8 Correct 130 ms 26704 KB Output is correct
9 Correct 135 ms 26652 KB Output is correct
10 Correct 152 ms 26816 KB Output is correct
11 Correct 233 ms 26704 KB Output is correct
12 Correct 328 ms 26708 KB Output is correct
13 Correct 758 ms 26856 KB Output is correct
14 Correct 2045 ms 27356 KB Output is correct
15 Execution timed out 5061 ms 28500 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
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 1 ms 604 KB Output is correct
4 Correct 3499 ms 19684 KB Output is correct
5 Correct 3463 ms 22372 KB Output is correct
6 Execution timed out 5051 ms 27728 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 3 ms 604 KB Output is correct
31 Correct 4 ms 604 KB Output is correct
32 Correct 5 ms 860 KB Output is correct
33 Correct 5 ms 852 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 5 ms 856 KB Output is correct
36 Correct 5 ms 860 KB Output is correct
37 Correct 5 ms 856 KB Output is correct
38 Correct 6 ms 1116 KB Output is correct
39 Correct 5 ms 1116 KB Output is correct
40 Correct 5 ms 1116 KB Output is correct
41 Correct 5 ms 1160 KB Output is correct
42 Correct 6 ms 1116 KB Output is correct
43 Correct 5 ms 1092 KB Output is correct
44 Correct 5 ms 860 KB Output is correct
45 Correct 5 ms 860 KB Output is correct
46 Correct 5 ms 860 KB Output is correct
47 Correct 5 ms 856 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 6 ms 856 KB Output is correct
50 Correct 4 ms 860 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 4 ms 860 KB Output is correct
54 Correct 5 ms 856 KB Output is correct
55 Correct 4 ms 860 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 4 ms 836 KB Output is correct
58 Correct 5 ms 860 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 2 ms 604 KB Output is correct
62 Correct 3315 ms 26240 KB Output is correct
63 Correct 4074 ms 33348 KB Output is correct
64 Correct 4122 ms 38704 KB Output is correct
65 Execution timed out 5052 ms 43340 KB Time limit exceeded
66 Halted 0 ms 0 KB -