oj.uz

Submission #933947

# Submission time Handle Problem Language Result Execution time Memory
933947 2024-02-26T15:27:38 Z boris_mihov Tourism (JOI23_tourism) C++17
17 / 100
 5000 ms 45512 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <cmath>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 18;
const int INF  = 1e9;

int n, m, q;
int in[MAXN];
int out[MAXN];
int globalCost;
bool isInC[MAXN];
std::vector <int> notInC;
std::vector <int> inTimes;
int cnt[2 * MAXN];
int c[MAXN];

struct LinkedList
{
    struct Sparse
    {
        int sparse[MAXLOG][2 * MAXN];
        std::vector <int> tour;
        int getLog[2 * MAXN];
        int depth[MAXN];

        int cmp(int x, int y)
        {
            if (depth[x] < depth[y]) return x;
            else return y;
        }

        void build(std::vector <int> _tour, int dep[])
        {
            tour = _tour;
            for (int i = 1 ; i <= n ; ++i)
            {
                depth[i] = dep[i];
            }

            for (int i = 1 ; i < tour.size() ; ++i)
            {
                sparse[0][i] = tour[i];
            }

            for (int lg = 1 ; (1 << lg) <= tour.size() ; ++lg)
            {
                for (int i = 1 ; i + (1 << lg) - 1 < tour.size() ; ++i)
                {
                    sparse[lg][i] = cmp(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
                }
            }

            for (int i = 1 ; i <= tour.size() ; ++i)
            {
                getLog[i] = getLog[i - 1];
                if ((1 << getLog[i] + 1) < i) getLog[i]++;
            }
        }

        int findLCA(int l, int r)
        {
            int lg = getLog[r - l + 1];
            return cmp(sparse[lg][l], sparse[lg][r - (1 << lg) + 1]);
        }

        int findDist(int u, int v)
        {
            if (in[u] > in[v])
            {
                std::swap(u, v);
            }

            return depth[u] + depth[v] - 2 * depth[findLCA(in[u], in[v])];
        }
    };

    struct RollElement
    {
        int *element;
        int value;
        int time;
    };

    int answer;
    int prev[2 * MAXN];
    int next[2 * MAXN];
    std::stack <RollElement> st;
    std::vector <int> tour;
    Sparse sparse;
    int timer;

    void build(std::vector <int> _tour, int depth[])
    {
        tour = _tour;
        sparse.build(tour, depth);
    }

    void rebuild()
    {
        while (st.size())
        {
            st.pop();
        }

        int ptr = 0;
        for (int i = 0 ; i <= tour.size() ; ++i)
        {
            while (inTimes[ptr] <= i)
            {
                ptr++;
            }

            next[i] = inTimes[ptr];
        }

        ptr = inTimes.size() - 1;
        for (int i = tour.size() ; i >= 0 ; --i)
        {
            while (inTimes[ptr] >= i)
            {
                ptr--;
            }

            prev[i] = inTimes[ptr];
        }

        std::fill(cnt, cnt + 1 + 2 * n, 0);
        for (int i = 1 ; i <= m ; ++i)
        {
            cnt[in[c[i]]]++;
        }

        answer = 2 * n - 2 - sparse.findDist(tour[next[0]], tour[prev[tour.size()]]);
        timer = 0;

        for (const int &i : notInC)
        {
            remove(in[i]);
        }

    }

    void roll(int to)
    {
        while (st.size() && st.top().time > to)
        {
            *st.top().element = st.top().value;
            st.pop();
        }
    }

    void remove(int idx)
    {
        timer++;
        st.push({&cnt[idx], cnt[idx], timer});
        cnt[idx]--;

        if (cnt[idx] > 0)
        {
            return;
        }

        int l = prev[idx];
        int r = next[idx];
        st.push({&answer, answer, timer});
        st.push({&next[l], next[l], timer});
        st.push({&prev[r], prev[r], timer});

        if (l > 0) answer -= sparse.findDist(tour[l], tour[idx]);
        if (r < tour.size()) answer -= sparse.findDist(tour[idx], tour[r]);
        if (l > 0 && r < tour.size()) answer += sparse.findDist(tour[l], tour[r]);
        next[l] = r;
        prev[r] = l;
        getAnswer();
    }

    int getAnswer()
    {
        int res = answer;
        res += sparse.findDist(tour[next[0]], tour[prev[tour.size()]]);
        assert(res % 2 == 0);
        return res / 2 + 1;
    }
};

int bucketSize;
LinkedList list;
struct Query
{
    int l, r;
    int idx;

    friend bool operator < (const Query &a, const Query &b)
    {
        if (a.l / bucketSize != b.l / bucketSize) return a.l < b.l;
        return a.r > b.r;
    }
};

int depth[MAXN];
int answer[MAXN];
std::vector <int> tour;
std::vector <int> g[MAXN];
Query query[MAXN];

void buildDFS(int node, int par)
{
    depth[node] = depth[par] + 1;
    in[node] = tour.size();
    tour.push_back(node);

    for (const int &u : g[node])
    {
        if (u == par)
        {
            continue;
        }

        buildDFS(u, node);
        tour.push_back(node);
    }
    
    out[node] = tour.size();
}

void solve()
{
    bucketSize = sqrt(m);
    tour.push_back(0);
    buildDFS(1, 0);

    for (int i = 1 ; i <= n ; ++i)
    {
        inTimes.push_back(in[i]);
    }

    inTimes.push_back(-1);
    inTimes.push_back(0);
    inTimes.push_back(tour.size());
    inTimes.push_back(tour.size() + 1);
    std::sort(inTimes.begin(), inTimes.end());
    for (int i = 1 ; i <= m ; ++i)
    {
        isInC[c[i]] = true;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (!isInC[i])
        {
            notInC.push_back(i);
        }
    }

    list.build(tour, depth);

    int lPtr = 1;
    int rPtr = m;
    int lastBucket = -1;
    std::sort(query + 1, query + 1 + q);
    for (int i = 1 ; i <= q ; ++i)
    {
        int qL = query[i].l;
        int qR = query[i].r;

        if (qL / bucketSize != lastBucket)
        {
            lPtr = 1;
            rPtr = m;
            list.rebuild();
            lastBucket = qL / bucketSize;
            while (lPtr / bucketSize != lastBucket)
            {
                list.remove(in[c[lPtr]]);
                lPtr++;
            }
        }

        while (rPtr > qR)
        {
            list.remove(in[c[rPtr]]);
            rPtr--;
        }

        int rollTo = list.timer;
        int beforeL = lPtr;

        while (lPtr < qL)
        {
            list.remove(in[c[lPtr]]);
            lPtr++;
        }

        answer[query[i].idx] = list.getAnswer();
        lPtr = beforeL;
        list.getAnswer();
        list.roll(rollTo);
        list.getAnswer();
    }
}

void input()
{
    std::cin >> n >> m >> q;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> c[i];
    }

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

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();
    
    return 0;
}

Compilation message

tourism.cpp: In member function 'void LinkedList::Sparse::build(std::vector<int>, int*)':
tourism.cpp:50:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int i = 1 ; i < tour.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~
tourism.cpp:55:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int lg = 1 ; (1 << lg) <= tour.size() ; ++lg)
      |                               ~~~~~~~~~~^~~~~~~~~~~~~~
tourism.cpp:57:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 for (int i = 1 ; i + (1 << lg) - 1 < tour.size() ; ++i)
      |                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
tourism.cpp:59:88: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |                     sparse[lg][i] = cmp(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
      |                                                                                     ~~~^~~
tourism.cpp:63:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for (int i = 1 ; i <= tour.size() ; ++i)
      |                              ~~^~~~~~~~~~~~~~
tourism.cpp:66:37: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   66 |                 if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                           ~~~~~~~~~~^~~
tourism.cpp: In member function 'void LinkedList::rebuild()':
tourism.cpp:116:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int i = 0 ; i <= tour.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
tourism.cpp: In member function 'void LinkedList::remove(int)':
tourism.cpp:180:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         if (r < tour.size()) answer -= sparse.findDist(tour[idx], tour[r]);
      |             ~~^~~~~~~~~~~~~
tourism.cpp:181:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         if (l > 0 && r < tour.size()) answer += sparse.findDist(tour[l], tour[r]);
      |                      ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12712 KB Output is correct
3 Correct 2 ms 14816 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16728 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16920 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 3 ms 18776 KB Output is correct
14 Correct 3 ms 18924 KB Output is correct
15 Correct 3 ms 19032 KB Output is correct
16 Correct 3 ms 18780 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 3 ms 18780 KB Output is correct
21 Correct 3 ms 18780 KB Output is correct
22 Correct 4 ms 19036 KB Output is correct
23 Correct 3 ms 18776 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 3 ms 18780 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 18972 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12712 KB Output is correct
3 Correct 2 ms 14816 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16728 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16920 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 3 ms 18776 KB Output is correct
14 Correct 3 ms 18924 KB Output is correct
15 Correct 3 ms 19032 KB Output is correct
16 Correct 3 ms 18780 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 3 ms 18780 KB Output is correct
21 Correct 3 ms 18780 KB Output is correct
22 Correct 4 ms 19036 KB Output is correct
23 Correct 3 ms 18776 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 3 ms 18780 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 18972 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct
30 Correct 8 ms 19036 KB Output is correct
31 Correct 13 ms 19036 KB Output is correct
32 Correct 12 ms 19284 KB Output is correct
33 Correct 13 ms 19292 KB Output is correct
34 Correct 13 ms 19280 KB Output is correct
35 Correct 5 ms 19036 KB Output is correct
36 Correct 5 ms 19036 KB Output is correct
37 Correct 5 ms 19036 KB Output is correct
38 Correct 11 ms 19292 KB Output is correct
39 Correct 11 ms 19288 KB Output is correct
40 Correct 16 ms 19292 KB Output is correct
41 Correct 5 ms 19292 KB Output is correct
42 Correct 5 ms 19292 KB Output is correct
43 Correct 5 ms 19256 KB Output is correct
44 Correct 12 ms 19288 KB Output is correct
45 Correct 12 ms 19292 KB Output is correct
46 Correct 16 ms 19288 KB Output is correct
47 Correct 5 ms 19036 KB Output is correct
48 Correct 5 ms 19036 KB Output is correct
49 Correct 5 ms 19132 KB Output is correct
50 Correct 11 ms 19288 KB Output is correct
51 Correct 12 ms 19288 KB Output is correct
52 Correct 12 ms 19288 KB Output is correct
53 Correct 12 ms 19544 KB Output is correct
54 Correct 11 ms 19292 KB Output is correct
55 Correct 12 ms 19292 KB Output is correct
56 Correct 4 ms 10588 KB Output is correct
57 Correct 4 ms 19032 KB Output is correct
58 Correct 13 ms 19292 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 4 ms 10760 KB Output is correct
4 Correct 2183 ms 36208 KB Output is correct
5 Correct 2129 ms 40772 KB Output is correct
6 Correct 2967 ms 43196 KB Output is correct
7 Correct 3958 ms 45504 KB Output is correct
8 Correct 4048 ms 45512 KB Output is correct
9 Correct 4242 ms 45508 KB Output is correct
10 Correct 3986 ms 45504 KB Output is correct
11 Correct 4156 ms 45504 KB Output is correct
12 Correct 341 ms 40556 KB Output is correct
13 Correct 351 ms 40392 KB Output is correct
14 Correct 373 ms 40612 KB Output is correct
15 Correct 69 ms 43772 KB Output is correct
16 Correct 4236 ms 45000 KB Output is correct
17 Correct 646 ms 13536 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12772 KB Output is correct
2 Correct 1586 ms 31364 KB Output is correct
3 Correct 2483 ms 32276 KB Output is correct
4 Correct 2392 ms 33432 KB Output is correct
5 Correct 59 ms 32976 KB Output is correct
6 Correct 87 ms 35816 KB Output is correct
7 Correct 203 ms 37276 KB Output is correct
8 Correct 566 ms 37812 KB Output is correct
9 Correct 1583 ms 37852 KB Output is correct
10 Correct 4532 ms 37908 KB Output is correct
11 Correct 4646 ms 37928 KB Output is correct
12 Correct 4947 ms 37956 KB Output is correct
13 Correct 4902 ms 38296 KB Output is correct
14 Execution timed out 5060 ms 39132 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 2722 ms 32992 KB Output is correct
5 Correct 2853 ms 33376 KB Output is correct
6 Correct 4259 ms 37020 KB Output is correct
7 Correct 4810 ms 39248 KB Output is correct
8 Correct 4939 ms 39332 KB Output is correct
9 Execution timed out 5014 ms 39844 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12712 KB Output is correct
3 Correct 2 ms 14816 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16728 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16920 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Correct 3 ms 18776 KB Output is correct
13 Correct 3 ms 18776 KB Output is correct
14 Correct 3 ms 18924 KB Output is correct
15 Correct 3 ms 19032 KB Output is correct
16 Correct 3 ms 18780 KB Output is correct
17 Correct 3 ms 18780 KB Output is correct
18 Correct 3 ms 18780 KB Output is correct
19 Correct 4 ms 18780 KB Output is correct
20 Correct 3 ms 18780 KB Output is correct
21 Correct 3 ms 18780 KB Output is correct
22 Correct 4 ms 19036 KB Output is correct
23 Correct 3 ms 18776 KB Output is correct
24 Correct 3 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 3 ms 18780 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 18972 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct
30 Correct 8 ms 19036 KB Output is correct
31 Correct 13 ms 19036 KB Output is correct
32 Correct 12 ms 19284 KB Output is correct
33 Correct 13 ms 19292 KB Output is correct
34 Correct 13 ms 19280 KB Output is correct
35 Correct 5 ms 19036 KB Output is correct
36 Correct 5 ms 19036 KB Output is correct
37 Correct 5 ms 19036 KB Output is correct
38 Correct 11 ms 19292 KB Output is correct
39 Correct 11 ms 19288 KB Output is correct
40 Correct 16 ms 19292 KB Output is correct
41 Correct 5 ms 19292 KB Output is correct
42 Correct 5 ms 19292 KB Output is correct
43 Correct 5 ms 19256 KB Output is correct
44 Correct 12 ms 19288 KB Output is correct
45 Correct 12 ms 19292 KB Output is correct
46 Correct 16 ms 19288 KB Output is correct
47 Correct 5 ms 19036 KB Output is correct
48 Correct 5 ms 19036 KB Output is correct
49 Correct 5 ms 19132 KB Output is correct
50 Correct 11 ms 19288 KB Output is correct
51 Correct 12 ms 19288 KB Output is correct
52 Correct 12 ms 19288 KB Output is correct
53 Correct 12 ms 19544 KB Output is correct
54 Correct 11 ms 19292 KB Output is correct
55 Correct 12 ms 19292 KB Output is correct
56 Correct 4 ms 10588 KB Output is correct
57 Correct 4 ms 19032 KB Output is correct
58 Correct 13 ms 19292 KB Output is correct
59 Correct 2 ms 12636 KB Output is correct
60 Correct 2 ms 10588 KB Output is correct
61 Correct 4 ms 10760 KB Output is correct
62 Correct 2183 ms 36208 KB Output is correct
63 Correct 2129 ms 40772 KB Output is correct
64 Correct 2967 ms 43196 KB Output is correct
65 Correct 3958 ms 45504 KB Output is correct
66 Correct 4048 ms 45512 KB Output is correct
67 Correct 4242 ms 45508 KB Output is correct
68 Correct 3986 ms 45504 KB Output is correct
69 Correct 4156 ms 45504 KB Output is correct
70 Correct 341 ms 40556 KB Output is correct
71 Correct 351 ms 40392 KB Output is correct
72 Correct 373 ms 40612 KB Output is correct
73 Correct 69 ms 43772 KB Output is correct
74 Correct 4236 ms 45000 KB Output is correct
75 Correct 646 ms 13536 KB Output is correct
76 Correct 2 ms 12772 KB Output is correct
77 Correct 1586 ms 31364 KB Output is correct
78 Correct 2483 ms 32276 KB Output is correct
79 Correct 2392 ms 33432 KB Output is correct
80 Correct 59 ms 32976 KB Output is correct
81 Correct 87 ms 35816 KB Output is correct
82 Correct 203 ms 37276 KB Output is correct
83 Correct 566 ms 37812 KB Output is correct
84 Correct 1583 ms 37852 KB Output is correct
85 Correct 4532 ms 37908 KB Output is correct
86 Correct 4646 ms 37928 KB Output is correct
87 Correct 4947 ms 37956 KB Output is correct
88 Correct 4902 ms 38296 KB Output is correct
89 Execution timed out 5060 ms 39132 KB Time limit exceeded
90 Halted 0 ms 0 KB -