oj.uz

Submission #933960

# Submission time Handle Problem Language Result Execution time Memory
933960 2024-02-26T15:37:55 Z boris_mihov Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 40356 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 RollElementCnt
    {
        int idx;
        int time;
        int value;
    };

    
    struct RollElement
    {
        int idx;
        int value;
    };

    int answer;
    int prev[2 * MAXN];
    int next[2 * MAXN];
    std::stack <RollElement> stNext;
    std::stack <RollElement> stPrev;
    std::stack <RollElementCnt> stCnt;
    std::stack <int> stAnswer;
    std::stack <int> stTime;
    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 (stNext.size())
        {
            stNext.pop();
        }

        while (stPrev.size())
        {
            stPrev.pop();
        }

        while (stCnt.size())
        {
            stCnt.pop();
        }

        while (stAnswer.size())
        {
            stAnswer.pop();
        }

        while (stTime.size())
        {
            stTime.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 (stCnt.top().time > to)
        {
            cnt[stCnt.top().idx] = stCnt.top().value;
            stCnt.pop();
        }

        while (stTime.size() && stTime.top() > to)
        {
            next[stNext.top().idx] = stNext.top().value;
            prev[stPrev.top().idx] = stPrev.top().value;
            answer = stAnswer.top();
            stNext.pop();
            stTime.pop();
            stPrev.pop();
            stAnswer.pop();
        }
    }

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

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

        int l = prev[idx];
        int r = next[idx];
        stTime.push(timer);
        stAnswer.push(answer);
        stNext.push({l, next[l]});
        stPrev.push({r, prev[r]});

        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) / 2;
    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:147:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int i = 0 ; i <= tour.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
tourism.cpp: In member function 'void LinkedList::remove(int)':
tourism.cpp:223:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         if (r < tour.size()) answer -= sparse.findDist(tour[idx], tour[r]);
      |             ~~^~~~~~~~~~~~~
tourism.cpp:224:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         if (l > 0 && r < tour.size()) answer += sparse.findDist(tour[l], tour[r]);
      |                      ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 5 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 3 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 3 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 18780 KB Output is correct
17 Correct 4 ms 18776 KB Output is correct
18 Correct 4 ms 18780 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 4 ms 18776 KB Output is correct
21 Correct 4 ms 18780 KB Output is correct
22 Correct 3 ms 18780 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 4 ms 18840 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Runtime error 20 ms 37980 KB Execution killed with signal 8
29 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 5 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 3 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 3 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 18780 KB Output is correct
17 Correct 4 ms 18776 KB Output is correct
18 Correct 4 ms 18780 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 4 ms 18776 KB Output is correct
21 Correct 4 ms 18780 KB Output is correct
22 Correct 3 ms 18780 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 4 ms 18840 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Runtime error 20 ms 37980 KB Execution killed with signal 8
29 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 10684 KB Output is correct
3 Correct 5 ms 10584 KB Output is correct
4 Correct 3523 ms 33072 KB Output is correct
5 Correct 3433 ms 37036 KB Output is correct
6 Correct 4405 ms 39004 KB Output is correct
7 Execution timed out 5030 ms 40356 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2944 ms 29000 KB Output is correct
3 Correct 4723 ms 29652 KB Output is correct
4 Execution timed out 5047 ms 30112 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 5 ms 10584 KB Output is correct
4 Correct 3953 ms 29936 KB Output is correct
5 Correct 4405 ms 30172 KB Output is correct
6 Execution timed out 5032 ms 32412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 5 ms 18776 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 3 ms 18780 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 3 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 18780 KB Output is correct
17 Correct 4 ms 18776 KB Output is correct
18 Correct 4 ms 18780 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 4 ms 18776 KB Output is correct
21 Correct 4 ms 18780 KB Output is correct
22 Correct 3 ms 18780 KB Output is correct
23 Correct 4 ms 18780 KB Output is correct
24 Correct 4 ms 18780 KB Output is correct
25 Correct 3 ms 18780 KB Output is correct
26 Correct 4 ms 18840 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Runtime error 20 ms 37980 KB Execution killed with signal 8
29 Halted 0 ms 0 KB -