Submission #794056

#	Time	Username	Problem	Language	Result	Execution time	Memory
794056		vjudge1	Tourism (JOI23_tourism)	C++14	35 / 100	1354 ms	47336 KiB

tourism

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 17), sz = 317 ;
bool flag1, flag2, flag3, 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], answer[N + 1] ;
vector<int> v[N + 1] ;
vector<pair<int, int>> tree ;
int mx[N + 1][20], mn1[N + 1][20], mg[N + 1][20] ;
pair<int, int> mn[2 * N + 1][20] ;
vector<int> hld ;
int kol[N + 1], index1[N + 1], tp[N + 1], bst[N + 1], sum[2 * N + 1], psh[2 * N + 1] ;
struct query
{
    int l, r, ind ;
};
bool cmp(query q1, query q2)
{
    if(q1.l / sz != q2.l / sz)
        return q1.l / sz < q2.l / sz ;
    else
        return q1.r < q2.r ;
}
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])} ;
}
//всё ниже для MO's algorithm
int cnt[N + 1], sm[2 * N + 1] ;
void build_mega_lca()
{
    for(int i = 2 ; i <= m ; i++)
        pw[i] = pw[i / 2] + 1 ;
    for(int i = 1 ; i <= m ; i++)
        mg[i][0] = c[i] ;
    for(int i = 1 ; i < 20 ; i++)
        for(int j = 1 ; j <= n - (1 << i) + 1 ; j++)
            mg[j][i] = get_lca(mg[j][i - 1], mg[j + (1 << (i - 1))][i - 1]) ;
}
int get_mega_lca(int a, int b)
{
    int num = pw[b - a + 1] ;
    return get_lca(mg[a][num], mg[b - (1 << num) + 1][num]) ;
}
void del(int ind)
{
    while(ind)
    {
        sm[ind] = sm[ind * 2] + sm[ind * 2 + 1] + 1 ;
        cnt[ind]-- ;
        if(!cnt[ind])sm[ind]-- ;
        ind >>= 1 ;
    }
}
void add(int ind)
{
    while(ind)
    {
        sm[ind] = sm[ind * 2] + sm[ind * 2 + 1] + (cnt[ind] > 0) ;
        if(!cnt[ind])sm[ind]++ ;
        cnt[ind]++ ;
        ind >>= 1 ;
    }
}
//конец
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 ;
        if(a != (i + 1) / 2 || b != i + 1)flag3 = 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(!flag3)
    {
        dfs(1, 0) ;
        build_lca() ;
        build_mega_lca() ;
        int ln = 0, rn = -1 ;
        vector<query> qr ;
        for(int i = 1 ; i <= q ; i++)
        {
            query q ;
            q.l = l[i] - 1 ;
            q.r = r[i] - 1 ;
            q.ind = i ;
            qr.push_back(q) ;
        }
        sort(qr.begin(), qr.end(), cmp) ;
        for(query i : qr)
        {
            int j = i.ind, lc = get_mega_lca(i.l + 1, i.r + 1) ;
//            cout<<j << ' '<<i.l<<' '<<i.r<<' '<<lc << ' ' << ln << ' '<< rn << '\n' ;
            while(rn < i.r)
            {
                rn++ ;
                add(c[rn + 1]) ;
            }
//            cout<<j << ' '<<i.l<<' '<<i.r<<' '<<lc << ' ' << ln << ' '<< rn << '\n' ;
            while(ln > i.l)
            {
                ln-- ;
                add(c[ln + 1]) ;
            }
//            cout<<j << ' '<<i.l<<' '<<i.r<<' '<<lc << ' ' << ln << ' '<< rn << '\n' ;
            while(rn > i.r)
            {
                del(c[rn + 1]) ;
                rn-- ;
            }
//            cout<<j << ' '<<i.l<<' '<<i.r<<' '<<lc << ' ' << ln << ' '<< rn << '\n' ;
            while(ln < i.l)
            {
                del(c[ln + 1]) ;
                ln++ ;
            }
//            cout<<j << ' '<<i.l<<' '<<i.r<<' '<<lc << ' ' << ln << ' '<< rn << '\n' ;
            answer[j] = sm[lc] ;
        }
        for(int i = 1 ; i <= q ; i++)
            cout << answer[i] << '\n' ;
        return 0 ;
    }
    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' ;
            psh[1] = 0 ;
        }
        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 ;
}
//7 6 1
//1 2
//1 3
//2 4
//2 5
//3 6
//3 7
//2 3 6 4 5 7
//1 3

Compilation message (stderr)

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

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