oj.uz

답안 #1101619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101619 2024-10-16T11:52:53 Z Pacybwoah Tourism (JOI23_tourism) C++17
24 / 100
 5000 ms 32960 KB 
#include<iostream>
#include<vector>
#include<set>
#include<utility>
#include<cassert>
#include<algorithm>
using namespace std;
int n, m, q;
vector<vector<int>> graph, anc;
vector<int> vec, in, out, ord, head, sz, bit, dep;
int cnt = 0;
void dfs(int node, int parent){
    ord[++cnt] = node;
    in[node] = cnt;
    sz[node] = 1;
    anc[0][node] = parent;
    head[node] = node;
    dep[node] = dep[parent] + 1;
    int maxi = 0, pos = -1;
    for(auto &x: graph[node]){
        if(x == parent) continue;
        dfs(x, node);
        sz[node] += sz[x];
        if(maxi < sz[x]){
            maxi = sz[x];
            pos = x;
        }
    }
    if(pos > 0) head[pos] = node;
    out[node] = cnt;
}
void dfs_head(int node, int parent){
    if(head[node] != node) head[node] = head[parent];
    for(auto &x: graph[node]){
        if(x != parent) dfs_head(x, node);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    graph.resize(n + 1);
    vec.resize(m + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    ord.resize(n + 1);
    head.resize(n + 1);
    sz.resize(n + 1);
    dep.resize(n + 1);
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    anc.resize(18, vector<int>(n + 1));
    dfs(1, 1);
    //dfs_head(1, 1);
    for(int i = 1; i < 18; i++) for(int j = 1; j <= n; j++) anc[i][j] = anc[i - 1][anc[i - 1][j]];
    auto lca = [&](int a, int b){
        if(dep[a] < dep[b]) swap(a, b);
        for(int i = 0; i < 18; i++){
            if((dep[a] - dep[b]) & (1 << i)) a = anc[i][a];
        }
        for(int i = 17; i >= 0; i--){
            if(anc[i][a] != anc[i][b]){
                a = anc[i][a];
                b = anc[i][b];
            }
        }
        if(a != b) return anc[0][a];
        else return a;
    };
    bit.resize(m + 1);
    for(int i = 1; i <= m; i++) cin >> vec[i];
    auto modify = [&](int pos, int val){
        while(pos <= m){
            bit[pos] += val;
            pos += (pos & -pos);
        }
    };
    auto query = [&](int pos){
        int ans = 0;
        while(pos > 0){
            ans += bit[pos];
            pos -= (pos & -pos);
        }
        return ans;
    };
    vector<vector<pair<int, int>>> sweep(m + 1);
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        sweep[r].emplace_back(l, i);
    }
    vector<vector<int>> st(18, vector<int>(m));
    for(int i = 1; i < m; i++) st[0][i] = lca(vec[i], vec[i + 1]);
    for(int i = 1; i < 18; i++){
        for(int j = 1; j < m; j++) st[i][j] = lca(st[i - 1][j], st[i - 1][min(m - 1, j + (1 << (i - 1)))]);
    }
    vector<int> bases(m);
    for(int i = 2; i < m; i++){
        bases[i] = bases[i - 1];
        if((1 << (bases[i] + 1)) == i) bases[i]++;
    }
    auto qlca = [&](int l, int r){
        r--;
        if(l > r) return vec[l];
        int len = r - l + 1;
        return lca(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]);
    };
    set<pair<pair<int, int>, int>> s;
    auto assign = [&](int l, int r, int col){
        //cout << l << " " << r << " " << col << "\n";
        while(!s.empty()){
            auto iter = s.lower_bound(make_pair(make_pair(l, 0), 0));
            if(iter == s.end()) break;
            auto [rng, scol] = (*iter);
            if(rng.first > r) break;
            s.erase(iter);
            modify(scol, -(rng.second - rng.first + 1));
            if(rng.second > r){
                modify(scol, rng.second - r);
                s.insert(make_pair(make_pair(r + 1, rng.second), scol));
            }
        }
        auto iter2 = s.lower_bound(make_pair(make_pair(l, 0), 0));
        if(iter2 != s.begin()){
            iter2 = prev(iter2);
            if((*iter2).first.second >= l){
                auto [rng2, col2] = (*iter2);
                s.erase(iter2);
                modify(col2, -(rng2.second - l + 1));
                s.insert(make_pair(make_pair(rng2.first, l - 1), col2));
                if(r < rng2.second){
                    modify(col2, rng2.second - r);
                    s.insert(make_pair(make_pair(r + 1, rng2.second), col2));
                }
            }
        }
        s.insert(make_pair(make_pair(l, r), col));
        modify(col, r - l + 1);
    };
    for(int i = 1; i <= m; i++){
        int cur = vec[i];
        while(1){
            assign(in[head[cur]], in[cur], i);
            if(head[cur] == 1) break;
            cur = anc[0][head[cur]];
        }
        for(auto &[l, id]: sweep[i]){
            ans[id] += query(i) - query(l - 1);
            ans[id] -= dep[qlca(l, i)];
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] + 1 << "\n";
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Execution timed out 5099 ms 26328 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 736 KB Output is correct
4 Correct 633 ms 23536 KB Output is correct
5 Correct 625 ms 24300 KB Output is correct
6 Correct 681 ms 29976 KB Output is correct
7 Correct 722 ms 32904 KB Output is correct
8 Correct 731 ms 32796 KB Output is correct
9 Correct 728 ms 32892 KB Output is correct
10 Correct 712 ms 32928 KB Output is correct
11 Correct 722 ms 32704 KB Output is correct
12 Correct 703 ms 32728 KB Output is correct
13 Correct 683 ms 32960 KB Output is correct
14 Correct 143 ms 13504 KB Output is correct

Subtask #6
0 / 41.0

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