oj.uz

Submission #848197

# Submission time Handle Problem Language Result Execution time Memory
848197 2023-09-11T14:52:11 Z nguyentunglam Tourism (JOI23_tourism) C++17
7 / 100
 194 ms 33924 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int N = 1e5 + 10;

int sz[N], par[N], heavy[N], bit[N], b[N], st[N], root[N], ans[N], off[N];

int timer, n, m, q;

pair<int, int> lines[20][N];

vector<pair<int, int> > S[N], query[N];

int mn[N << 2], mx[N << 2];

vector<int> adj[N];

void dfs(int u) {
    sz[u] = 1;
    for(int &v : adj[u]) if (v != par[u]) {
        par[v] = u;
        dfs(v);
        sz[u] += sz[v];
        if (sz[heavy[u]] < sz[v]) heavy[u] = v;
    }
}

void hld(int u) {
    st[u] = ++timer;
    if (!root[u]) root[u] = u;

    if (heavy[u]) {
        root[heavy[u]] = root[u];
        hld(heavy[u]);
    }

    for(int &v : adj[u]) if (v != par[u] && v != heavy[u]) hld(v);
}

void add(int pos, int val) {
    while (pos <= n) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

void addrange(int l, int r, int val) {
    add(l, val); add(r + 1, -val);
}

int get(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

void build(int s, int l, int r) {
    if (l == r) {
        mn[s] = mx[s] = b[l];
        return;
    }
    int mid = l + r >> 1;
    build(s << 1, l, mid);
    build(s << 1 | 1, mid + 1, r);
    mn[s] = min(mn[s << 1], mn[s << 1 | 1]);
    mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
}

pair<int, int> get(int s, int l, int r, int from, int to) {
    if (l > to || r < from) return make_pair(1e9, -1e9);
    if (from <= l && r <= to) return make_pair(mn[s], mx[s]);
    int mid = l + r >> 1;
    int mn1, mx1; tie(mn1, mx1) = get(s << 1, l, mid, from, to);
    int mn2, mx2; tie(mn2, mx2) = get(s << 1 | 1, mid + 1, r, from, to);
    return make_pair(min(mn1, mn2), max(mx1, mx2));
}

int main() {
    #define task ""

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

    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }

    if (fopen (task".inp", "r"))  {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }

    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);
    }

    dfs(1); hld(1);

    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        vector<pair<int, int> > tmp;

        while (x) {
            tmp.emplace_back(st[root[x]], st[x]);
            x = par[root[x]];
        }

        reverse(all(tmp));

        for(int j = 0; j < tmp.size(); j++) lines[j][i] = tmp[j];
    }


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

    for(int k = 17; k >= 0; k--) {
        for(int i = 1; i <= m; i++) {
            S[i].clear();
            bit[i] = 0;
            b[i] = lines[k][i].second;
        }

        int last = 0, prel = 0;

        build(1, 1, m);

        for(int i = 1; i <= m; i++) {
            int l, r; tie(l, r) = lines[k][i];

            if (l != prel) prel = l, last = i;

            if (l) {
                while (!S[l].empty() && S[l].back().first <= r) {
                    int tail, j; tie(tail, j) = S[l].back(); S[l].pop_back();
                    int pre = S[l].empty() ? 1 : S[l].back().second + 1;
                    addrange(pre, j, -(tail - l + 1));
                }

                int pre = S[l].empty() ? 1 : S[l].back().second + 1;
                addrange(pre, i, r - l + 1);
                S[l].emplace_back(r, i);
            }

            for(auto &[j, idx] : query[i]) if (!off[idx]) {
                if (last <= j && l) {
                    int tmp1, tmp2; tie(tmp1, tmp2) = get(1, 1, m, j, i);
                    ans[idx] += tmp2 - tmp1 + 1;
                    off[idx] = 1;
                }
                else {
                    ans[idx] += get(j);
                }
            }
        }
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

Compilation message

tourism.cpp: In function 'void build(int, int, int)':
tourism.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = l + r >> 1;
      |               ~~^~~
tourism.cpp: In function 'std::pair<int, int> get(int, int, int, int, int)':
tourism.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = l + r >> 1;
      |               ~~^~~
tourism.cpp: In function 'int main()':
tourism.cpp:123:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int j = 0; j < tmp.size(); j++) lines[j][i] = tmp[j];
      |                        ~~^~~~~~~~~~~~
tourism.cpp:93:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:94:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:98:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:99:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Incorrect 3 ms 16984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Incorrect 3 ms 16984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 132 ms 25728 KB Output is correct
5 Correct 106 ms 27900 KB Output is correct
6 Correct 109 ms 29524 KB Output is correct
7 Correct 165 ms 32272 KB Output is correct
8 Correct 159 ms 32332 KB Output is correct
9 Correct 176 ms 32264 KB Output is correct
10 Correct 164 ms 32248 KB Output is correct
11 Correct 165 ms 32156 KB Output is correct
12 Correct 130 ms 31428 KB Output is correct
13 Correct 118 ms 31312 KB Output is correct
14 Correct 121 ms 31408 KB Output is correct
15 Correct 43 ms 26704 KB Output is correct
16 Correct 153 ms 31968 KB Output is correct
17 Correct 135 ms 20384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 59 ms 24944 KB Output is correct
3 Incorrect 99 ms 25680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 4 ms 15024 KB Output is correct
4 Incorrect 194 ms 33924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Incorrect 3 ms 16984 KB Output isn't correct
5 Halted 0 ms 0 KB -