oj.uz

Submission #789297

# Submission time Handle Problem Language Result Execution time Memory
789297 2023-07-21T09:01:26 Z 이동현(#10044) Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 22268 KB 
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> way(n);
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    vector<int> a(m);
    for(int i = 0; i < m; ++i){
        cin >> a[i];
        --a[i];
    }

    vector<int> dep(n);
    vector<vector<int>> spa(n, vector<int>(20));
    vector<int> in(n), ed(n);
    int inN = 0;

    auto dfs = [&](auto&&self, int x, int pr)->void{
        in[x] = ++inN;
        for(auto&nxt:way[x]){
            if(nxt == pr){
                continue;
            }

            dep[nxt] = dep[x] + 1;
            spa[nxt][0] = x;
            self(self, nxt, x);
        }
        ed[x] = inN;
    };

    dfs(dfs, 0, -1);
    for(int j = 1; j < 20; ++j){
        for(int i = 0; i < n; ++i){
            spa[i][j] = spa[spa[i][j - 1]][j - 1];
        }
    }

    auto getlca = [&](int x, int y){
        if(dep[x] > dep[y]){
            swap(dep[x], dep[y]);
        }

        for(int i = 19; i >= 0; --i){
            if(dep[y] - (1 << i) >= dep[x]){
                y = spa[y][i];
            }
        }
        if(x == y) return x;

        for(int i = 19; i >= 0; --i){
            if(spa[x][i] != spa[y][i]){
                x = spa[x][i];
                y = spa[y][i];
            }
        }

        return spa[x][0];
    };

    while(q--){
        int l, r;
        cin >> l >> r;
        --l, --r;

        vector<int> id;
        for(int i = l; i <= r; ++i){
            id.push_back(a[i]);
        }
        sort(id.begin(), id.end(), [&](int&x, int&y){return in[x] < in[y];});
        int up = id[0];
        for(int i = 1; i < r - l + 1; ++i){
            id.push_back(getlca(id[i - 1], id[i]));
            up = getlca(up, id[i]);
        }
        id.push_back(up);

        sort(id.begin(), id.end(), [&](int&x, int&y){return in[x] < in[y];});
        // for(auto&i:id){
        //     cout << i << ' ';
        // }
        // cout << endl;

        int ans = 0;
        int nxt = 1;
        auto sol = [&](auto&&self, int x)->void{
            while(nxt < (int)id.size() && in[id[nxt]] <= ed[id[x]]){
                ans += dep[id[nxt]] - dep[id[x]];
                ++nxt;
                self(self, nxt - 1);
            }
        };
        sol(sol, 0);

        cout << ans + 1 << '\n';
    }
    
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 3 ms 320 KB Output is correct
3 Correct 81 ms 456 KB Output is correct
4 Execution timed out 5070 ms 22268 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 75 ms 468 KB Output is correct
4 Execution timed out 5049 ms 22108 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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