제출 #933896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933896		boris_mihov	Tourism (JOI23_tourism)	C++17	28 / 100	5092 ms	29468 KiB

tourism

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int n, m, q;
int in[MAXN];
int out[MAXN];

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 = 0 ; i < tour.size() ; ++i)
        {
            sparse[0][i] = tour[i];
        }

        for (int lg = 1 ; (1 << lg) <= tour.size() ; ++lg)
        {
            for (int i = 0 ; 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])];
    }
};

int c[MAXN];
int depth[MAXN];
std::vector <int> tour;
std::vector <int> g[MAXN];
Sparse sparse;

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()
{
    buildDFS(1, 0);
    sparse.build(tour, depth);

    for (int i = 1 ; i <= q ; ++i)
    {
        std::vector <int> v;
        int l, r;
        std::cin >> l >> r;
        for (int idx = l ; idx <= r ; ++idx)
        {
            v.push_back(c[idx]);
        }

        std::sort(v.begin(), v.end(), [&](int x, int y)
        {
            return in[x] < in[y];
        });

        int dist = 0;
        for (int i = 0 ; i < v.size() ; ++i)
        {
            int next = (i + 1) % v.size();
            dist += sparse.findDist(v[i], v[next]);
        }
        
        assert(dist % 2 == 0);
        std::cout << dist / 2 + 1 << '\n';
    }
}

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];
    }
}

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

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

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In member function 'void Sparse::build(std::vector<int>, int*)':
tourism.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0 ; i < tour.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~
tourism.cpp:42:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int lg = 1 ; (1 << lg) <= tour.size() ; ++lg)
      |                           ~~~~~~~~~~^~~~~~~~~~~~~~
tourism.cpp:44:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for (int i = 0 ; i + (1 << lg) - 1 < tour.size() ; ++i)
      |                              ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
tourism.cpp:46:84: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |                 sparse[lg][i] = cmp(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
      |                                                                                 ~~~^~~
tourism.cpp:50:28: 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:53:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   53 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~
tourism.cpp: In function 'void solve()':
tourism.cpp:121:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for (int i = 0 ; i < v.size() ; ++i)
      |                          ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41