제출 #793611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793611		vjudge1	Tourism (JOI23_tourism)	C++14	10 / 100	65 ms	7272 KiB

tourism

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5, NS = 2000 ;
bool flag1 ;
bool us[NS + 1] ;
int n, m, q, c[N + 1], l[N + 1], r[N + 1], p[N + 1], dist[N + 1],ind[N + 1], pw[2 * N + 1] ;
vector<int> v[N + 1] ;
vector<pair<int, int>> tree ;
pair<int, int> mn_mx, mn[2 * N + 1][20] ;
void dfs(int city, int last)
{
    ind[city] = tree.size() ;
    tree.push_back({dist[city], city}) ;
    p[city] = last ;
    for(int i : v[city])
    {
        if(i == last)
            continue ;
        dist[i] = dist[city] + 1 ;
        dfs(i, city) ;
        tree.push_back({dist[city], city}) ;
    }
}
void build_lca()
{
    for(int i = 2 ; i <= tree.size() ; i++)
        pw[i] = pw[i / 2] + 1 ;
    for(int i = 0 ; i < tree.size() ; i++)
        mn[i][0] = tree[i] ;
    for(int i = 1 ; i < 20 ; i++)
        for(int j = 0 ; j <= (int)tree.size() - (1 << i) ; j++)
            mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]) ;
}
int get_lca(int a, int b)
{
    a = ind[a] ;
    b = ind[b] ;
    if(a > b)
        swap(a, b) ;
    int num = pw[b - a + 1] ;
    return min(mn[a][num], mn[b - (1 << num) + 1][num]).se ;
}
void build_mn_mx()
{
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m >> q ;
    for(int i = 1 ; i < n ; i++)
    {
        int a, b ;
        cin >> a >> b ;
        if(a != i || b != i + 1)flag1 = 1 ;
        v[a].push_back(b) ;
        v[b].push_back(a) ;
    }
    for(int i = 1 ; i <= m ; i++)
        cin >> c[i] ;
    for(int i = 1 ; i <= q ; i++)
        cin >> l[i] >> r[i] ;
    if(n <= 2000 && m <= 2000 && q <= 2000)
    {
        us[0] = 1 ;
        dfs(1, 0) ;
        build_lca() ;
        for(int i = 1 ; i <= q ; i++)
        {
            int ans = 0, lc ;
            lc = c[l[i]] ;
            for(int j = l[i] + 1 ; j <= r[i] ; j++)
                lc = get_lca(lc, c[j]) ;
            for(int j = l[i] ; j <= r[i] ; j++)
            {
                int now = c[j] ;
                while(!us[now])
                {
                    ans++ ;
                    us[now] = 1 ;
                    if(now == lc)
                        break ;
                    now = p[now] ;
                }
            }
            for(int i = 1 ; i <= n ; i++)
                us[i] = 0 ;
            cout << ans << '\n' ;
        }
        return 0 ;
    }
    if(!flag1)
    {
//        build_mx_mn() ;
    }
    return 0 ;
}
//8 8 1
//1 2
//2 3
//3 4
//4 5
//5 6
//6 7
//7 8
//8 6 4 3 5 2 4 7
//3 5

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

tourism.cpp: In function 'void build_lca()':
tourism.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 2 ; i <= tree.size() ; i++)
      |                     ~~^~~~~~~~~~~~~~
tourism.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0 ; i < tree.size() ; i++)
      |                     ~~^~~~~~~~~~~~~

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