oj.uz

답안 #1031417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031417 2024-07-22T20:12:58 Z Wael Tourism (JOI23_tourism) C++17
0 / 100
 2033 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct SegmentTree {
    int n;
    vector<int> sum;
    SegmentTree(int n) : n(n) {
        sum.assign(4 * n, 0);
    }

    void update(int i, int v) {
        update(i, v, 0, 0, n - 1);
    }   
    void update(int i, int v, int x, int lx, int rx) {
        if (lx == rx) {
            sum[x] += v;
            return;
        }
        int mid = (lx + rx) / 2;
        if (i <= mid) {
            update(i, v, 2 * x + 1, lx, mid);            
        } else {
            update(i, v, 2 * x + 2, mid + 1, rx);
        }
        sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, n - 1);
    }
    int get(int l, int r, int x, int lx, int rx) {
        if (lx > r || rx < l) return 0;
        if (l <= lx && rx <= r) return sum[x];
        int mid = (lx + rx) / 2;
        return get(l, r, 2 * x + 1, lx, mid) + get(l, r, 2 * x + 2, mid + 1, rx);
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> c(m);
    vector<vector<int>> indices(n);
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
        --c[i];
        indices[c[i]].push_back(i);
    }

    vector<int> l(q), r(q);
    for (int i = 0; i < q; ++i) {
        cin >> l[i] >> r[i];
        --l[i], --r[i];
    }

    vector<int> belong(m);
    vector<vector<int>> st(n);
    vector<vector<pair<int, int>>> update(m);
    
    auto addRange = [&](int l, int r) {
        if (l > r) return;
        update[l].push_back({l, 1});
        if (r + 1 < m) {
          update[r + 1].push_back({l, -1});
        }
    };

    function<void(int, int)> dfs = [&](int u, int p) {
        for (auto v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
            for (auto i : st[v]) {
                st[u].push_back(i);
            }
        }
        for (auto i : indices[u]) {
            st[u].push_back(i);
            belong[i] = u;
        }
        sort(st[u].begin(), st[u].end());

        if (st[u].size()) {
            addRange(0, st[u][0] - 1);
        } else {
            addRange(0, m - 1);
        }

        auto checkNext = [&](int i) {
            int next = (i + 1 < st[u].size() ? st[u][i + 1] - 1 : m - 1);
            addRange(st[u][i] + 1, next);
        };

        for (int i = 0; i < st[u].size(); ++i) {
            checkNext(i);
            if (belong[st[u][i]] == u) continue;
            int j = i;
            while (j + 1 < st[u].size() && st[u][j] + 1 == st[u][j + 1] && belong[st[u][j]] == belong[st[u][j + 1]]) {
                ++j;
            }
            addRange(st[u][i], st[u][j]);
            i = j;
            if (j != i) {
                checkNext(j);
            }
        }

        for (auto i : st[u]) {
            belong[i] = u;
        }
    };      
    dfs(0, -1);

    vector<vector<int>> query(m);
    for (int i = 0; i < q; ++i) {
        query[r[i]].push_back(i);
    }

    vector<int> ans(q);
    SegmentTree seg(m);
    for (int i = 0; i < m; ++i) {
        for (auto [j, v] : update[i]) {
            seg.update(j, v);
        }
        for (auto j : query[i]) {
            ans[j] = n - seg.get(0, l[j]);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Compilation message

tourism.cpp: In lambda function:
tourism.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             int next = (i + 1 < st[u].size() ? st[u][i + 1] - 1 : m - 1);
      |                         ~~~~~~^~~~~~~~~~~~~~
tourism.cpp: In lambda function:
tourism.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i = 0; i < st[u].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
tourism.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while (j + 1 < st[u].size() && st[u][j] + 1 == st[u][j + 1] && belong[st[u][j]] == belong[st[u][j + 1]]) {
      |                    ~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Runtime error 2033 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 198 ms 44116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 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 Incorrect 432 ms 74008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -