oj.uz

Submission #848194

# Submission time Handle Problem Language Result Execution time Memory
848194 2023-09-11T14:41:51 Z nguyentunglam Tourism (JOI23_tourism) C++17
0 / 100
 78 ms 26572 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(auto &[l, r] : tmp) cout << l << " " << r << endl;
    }


    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 <= n; i++) {
            S[i].clear();
            bit[i] = 0;
            b[i] = lines[k][i].second;
        }

        int last = 0, prel = 0;

        build(1, 1, n);

        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, n, 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 4 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 4 ms 16988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 16988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 62 ms 25824 KB Output is correct
3 Incorrect 78 ms 26572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 16988 KB Output isn't correct
5 Halted 0 ms 0 KB -