Submission #793839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
793839	2023-07-26T07:18:42 Z	vjudge1	Tourism (JOI23_tourism)	C++14	7 / 100	82 ms	24508 KB

tourism

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 17) ;
bool flag1, flag2, us[N + 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 ;
int mx[N + 1][20], mn1[N + 1][20] ;
pair<int, int> mn[2 * N + 1][20] ;
//ниже всё для hld
vector<int> hld ;
int kol[N + 1], index1[N + 1], tp[N + 1], bst[N + 1], sum[2 * N + 1], psh[2 * N + 1] ;
void first_dfs(int city, int last)
{
    int now = 0 ;
    kol[city]++ ;
    for(int i : v[city])
    {
        if(i == last)
            continue ;
        first_dfs(i, city) ;
        kol[city] += kol[i] ;
        if(now < kol[i])
        {
            now = kol[i] ;
            bst[city] = i ;
        }
    }
}
void second_dfs(int city, int last, int gay)
{
    tp[city] = gay ;
    index1[city] = hld.size() ;
    hld.push_back(city) ;
    if(bst[city])
        second_dfs(bst[city], city, gay) ;
    for(int i : v[city])
    {
        if(i == last || i == bst[city])
            continue ;
        second_dfs(i, city, hld.size()) ;
    }
}
void push(int l, int r, int v)
{
    if(psh[v] == -1)
        return ;
    int num = psh[v] ;
    psh[v] = -1 ;
    sum[v] = num * (r - l + 1) ;
    if(l == r)
        return ;
    psh[v * 2] = num ;
    psh[v * 2 + 1] = num ;
}
void build()
{
    for(int i = 1 ; i <= 2 * N ; i++)
        psh[i] = -1 ;
}
void update(int l, int r, int l1, int r1, int num, int v)
{
    push(l, r, v) ;
    if(l > r1 || r < l1)
        return ;
    if(l1 <= l && r <= r1)
    {
        psh[v] = num ;
        push(l, r, v) ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update(l, mid, l1, r1, num, v * 2) ;
    update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
    sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
//конец hld
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_mx_mn()
{
    for(int i = 2 ; i <= m ; i++)
        pw[i] = pw[i / 2] + 1 ;
    for(int i = 1 ; i <= m ; i++)
        mn1[i][0] = c[i], mx[i][0] = c[i] ;
    for(int i = 1 ; i < 20 ; i++)
        for(int j = 1 ; j <= m - (1 << i) + 1 ; j++)
            mn1[j][i] = min(mn1[j][i - 1], mn1[j + (1 << (i - 1))][i - 1]),
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]) ;
}
pair<int, int> get_mn_mx(int a, int b)
{
    int num = pw[b - a + 1] ;
    return {min(mn1[a][num], mn1[b - (1 << num) + 1][num]), max(mx[a][num], mx[b - (1 << num) + 1][num])} ;
}
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] ;
    for(int i = 1 ; i < q ; i++)
        if(r[i] + 1 != l[i + 1])
            flag2 = 1 ;
    if(!flag2)
    {
        dfs(1, 0) ;
        build_lca() ;
        first_dfs(1, 0) ;
        second_dfs(1, 0, 0) ;
        build() ;
        for(int i = 1 ; i <= q ; i++)
        {
            int 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(now != p[lc])
                    if(index1[lc] < tp[now])
                    {
                        update(0, N - 1, tp[now], index1[now], 1, 1) ;
                        now = p[hld[tp[now]]] ;
                    }
                    else
                    {
                        update(0, N - 1, index1[lc], index1[now], 1, 1) ;
                        now = p[lc] ;
                    }
            }
            cout << sum[1] << '\n' ;
        }
        return 0 ;
    }
    if(!flag1)
    {
        build_mx_mn() ;
        for(int i = 1 ; i <= q ; i++)
        {
            pair<int, int> p = get_mn_mx(l[i], r[i]) ;
            cout << p.se - p.fi + 1 << '\n' ;
        }
        return 0 ;
    }
    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 = 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 ;
    }
    return 0 ;
}
//4 2 1
//1 2
//1 3
//1 4
//3 4
//1 2

Compilation message

tourism.cpp: In function 'void build_lca()':
tourism.cpp:97: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]
   97 |     for(int i = 2 ; i <= tree.size() ; i++)
      |                     ~~^~~~~~~~~~~~~~
tourism.cpp:99: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]
   99 |     for(int i = 0 ; i < tree.size() ; i++)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4436 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4436 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3412 KB	Output is correct
2	Correct	2 ms	3412 KB	Output is correct
3	Correct	2 ms	3796 KB	Output is correct
4	Correct	46 ms	20724 KB	Output is correct
5	Correct	41 ms	16164 KB	Output is correct
6	Correct	47 ms	20556 KB	Output is correct
7	Correct	76 ms	24508 KB	Output is correct
8	Correct	82 ms	24312 KB	Output is correct
9	Correct	63 ms	24392 KB	Output is correct
10	Correct	65 ms	24392 KB	Output is correct
11	Correct	63 ms	24272 KB	Output is correct
12	Correct	58 ms	24400 KB	Output is correct
13	Correct	56 ms	24332 KB	Output is correct
14	Correct	54 ms	24320 KB	Output is correct
15	Correct	33 ms	7440 KB	Output is correct
16	Correct	59 ms	23900 KB	Output is correct
17	Correct	41 ms	20780 KB	Output is correct