oj.uz

Submission #884150

# Submission time Handle Problem Language Result Execution time Memory
884150 2023-12-06T16:12:58 Z fanwen Tourism (JOI23_tourism) C++17
18 / 100
 341 ms 13876 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

#ifdef LOCAL
    #include "debug.h"
#else
    #define clog if(false) cerr
#endif

template <class T> struct Fenwick_Tree {
    vector<T> bit;
    int n;
    Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}

    void clear() { fill(bit.begin(), bit.end(), T(0)); }

    void update(int u, T val) {
        for (; u <= n; u += u & -u) bit[u] += val;
    }

    T get(int u) {
        T ans = 0;
        for (; u; u -= u & -u) ans += bit[u];
        return ans;
    }

    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
};


const int MAX = 1e5 + 5;

int n, m, q, c[MAX], ans[MAX], local[MAX], depth[MAX], header[MAX], par[MAX];
int numChild[MAX];
vector <int> adj[MAX];
vector <pair <int, int>> queries[MAX];

void dfs(int u, int p) {
    numChild[u] = 1;
    int Max = 0, id = 0;
    for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
        int v = adj[u][i];
        dfs(v, u);
        numChild[u] += numChild[v];
        if(Max < numChild[v]) {
            Max = numChild[v];
            id = i;
        }
    }
    swap(adj[u][0], adj[u][id]);
}

void dfs_hld(int u, int p) {
    static int run = 0;
    local[u] = ++run;
    par[u] = p;
    for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
        int v = adj[u][i];
        if(i == 0 && numChild[v] * 2 >= numChild[u]) {
            header[v] = header[u], depth[v] = depth[u];
        } else {
            header[v] = v;
            depth[v] = depth[u] + 1;
        }
        dfs_hld(v, u);
    }
}

int it[4 * MAX];

Fenwick_Tree <int> bit;

void pushdown(int idx) {
    if(it[idx] == -1) return;
    it[idx << 1] = it[idx << 1 | 1] = it[idx];
}

void update(int idx, int l, int r, int u, int v, int val) {
    if(l > v || r < u) return;
    if(l >= u && r <= v && it[idx] >= 0) {
        if(it[idx] > 0) bit.update(it[idx], - (r - l + 1));
        bit.update(it[idx] = val, r - l + 1);
        return;
    }

    pushdown(idx);

    int mid = l + r >> 1;
    update(idx << 1, l, mid, u, v, val);
    update(idx << 1 | 1, mid + 1, r, u, v, val);
    it[idx] = (it[idx << 1] == it[idx << 1 | 1] ? it[idx << 1] : -1);
}

void update_hld(int u, int v, int val) {
    while(header[u] != header[v]) {
        if(local[header[u]] < local[header[v]]) swap(u, v);
        update(1, 1, n, local[header[u]], local[u], val);
        u = par[header[u]];
    }
    update(1, 1, n, min(local[u], local[v]), max(local[u], local[v]), val);
}

void you_make_it(void) {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i) cin >> c[i];
    dfs(1, 0); depth[1] = header[1] = 1; dfs_hld(1, 0);

    fill(ans + 1, ans + q + 1, 1);
    for (int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        if(l < r) queries[l].emplace_back(r, i);
    }

    bit = Fenwick_Tree <int> (m);
    for (int i = m - 1; i >= 1; --i) {
        update_hld(c[i], c[i + 1], i + 1);
        for (auto [r, id] : queries[i]) ans[id] = bit.get(r);
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("tourism");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_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

tourism.cpp: In function 'void update(int, int, int, int, int, int)':
tourism.cpp:95:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |     int mid = l + r >> 1;
      |               ~~^~~
tourism.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
tourism.cpp:78:20:   required from here
tourism.cpp:17:9: warning: 'Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   17 |     int n;
      |         ^
tourism.cpp:16:15: warning:   'std::vector<int> Fenwick_Tree<int>::bit' [-Wreorder]
   16 |     vector<T> bit;
      |               ^~~
tourism.cpp:18:5: warning:   when initialized here [-Wreorder]
   18 |     Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |     ^~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:140:5: note: in expansion of macro 'file'
  140 |     file("tourism");
      |     ^~~~
tourism.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:140:5: note: in expansion of macro 'file'
  140 |     file("tourism");
      |     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8584 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8536 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8632 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Runtime error 6 ms 12924 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8584 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8536 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8632 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Runtime error 6 ms 12924 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Runtime error 6 ms 12892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 131 ms 10976 KB Output is correct
3 Correct 216 ms 11604 KB Output is correct
4 Correct 153 ms 11612 KB Output is correct
5 Correct 251 ms 12880 KB Output is correct
6 Correct 245 ms 12852 KB Output is correct
7 Correct 246 ms 12852 KB Output is correct
8 Correct 255 ms 12860 KB Output is correct
9 Correct 256 ms 12856 KB Output is correct
10 Correct 247 ms 12864 KB Output is correct
11 Correct 238 ms 12892 KB Output is correct
12 Correct 254 ms 12952 KB Output is correct
13 Correct 243 ms 13136 KB Output is correct
14 Correct 255 ms 13704 KB Output is correct
15 Correct 274 ms 13080 KB Output is correct
16 Correct 239 ms 13140 KB Output is correct
17 Correct 248 ms 13168 KB Output is correct
18 Correct 242 ms 13136 KB Output is correct
19 Correct 284 ms 12880 KB Output is correct
20 Correct 308 ms 13044 KB Output is correct
21 Correct 309 ms 12636 KB Output is correct
22 Correct 289 ms 13132 KB Output is correct
23 Correct 282 ms 12904 KB Output is correct
24 Correct 301 ms 12892 KB Output is correct
25 Correct 302 ms 12876 KB Output is correct
26 Correct 341 ms 12932 KB Output is correct
27 Correct 283 ms 12884 KB Output is correct
28 Correct 296 ms 12888 KB Output is correct
29 Correct 309 ms 12956 KB Output is correct
30 Correct 335 ms 13080 KB Output is correct
31 Correct 307 ms 13204 KB Output is correct
32 Correct 301 ms 13404 KB Output is correct
33 Correct 310 ms 13876 KB Output is correct
34 Correct 306 ms 13184 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Runtime error 8 ms 12996 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8584 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8536 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8632 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Runtime error 6 ms 12924 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -