Submission #1303233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303233		nhinconmemay	Tourism (JOI23_tourism)	C++20	35 / 100	5090 ms	35704 KiB

tourism

#include <bits/stdc++.h>

using namespace std ;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define FOR(i ,a , b) for(int i = a ; i <= b ; ++i)
#define name "task"

const ll N = 100000 + 5 ;
const ll LOG = 18 ;

ll n , m , q ;
ll h[N] , par[N][LOG + 1] ;
ll in[N] , siz[N] , cntDFS = 0 ;
ll S , id[N] , ANS[N] , c[N] ;

vector<ll> a[N] ;
set<ll> st ;
ll cntNode[N];
ll DIST = 0 ;

struct query {
    ll l , r , id ;
} Q[N];

void dfs(ll u , ll p)
{
    in[u] = ++cntDFS ;
    siz[u] = 1 ;
    par[u][0] = p ;
    for(ll v : a[u])
    {
        if(v == p) continue ;
        h[v] = h[u] + 1 ;
        dfs(v , u) ;
        siz[u] += siz[v] ;
    }
}

ll lca(ll u , ll v)
{
    if(h[u] < h[v]) swap(u , v) ;
    for(int j = LOG ; j >= 0 ; --j)
        if(par[u][j] && h[par[u][j]] >= h[v])
            u = par[u][j] ;

    if(u == v) return u ;

    for(int j = LOG ; j >= 0 ; --j)
        if(par[u][j] != par[v][j])
            u = par[u][j] , v = par[v][j] ;

    return par[u][0] ;
}

ll dist(ll u , ll v)
{
    return h[u] + h[v] - 2 * h[lca(u , v)] ;
}

bool cmp(query x, query y)
{
    if (x.l / S != y.l / S)
        return x.l / S < y.l / S;
    return (x.l / S) & 1 ? x.r < y.r : x.r > y.r;
}

ll getPrev(ll x)
{
    auto it = st.lower_bound(in[x]);
    if(it == st.begin()) it = st.end();
    --it;
    return id[*it];
}

ll getNext(ll x)
{
    auto it = st.upper_bound(in[x]);
    if(it == st.end()) it = st.begin();
    return id[*it];
}

void add(ll pos)
{
    ll u = c[pos];
    if (++cntNode[u] > 1) return;

    if(st.empty())
    {
        st.insert(in[u]);
        return;
    }
    ll L = getPrev(u);
    ll R = getNext(u);
    DIST += dist(L, u) + dist(u, R) - dist(L, R);
    st.insert(in[u]);
}

void del(ll pos)
{
    ll u = c[pos];
    if (--cntNode[u] > 0) return;

    if(st.size() == 1)
    {
        st.erase(in[u]);
        return;
    }
    ll L = getPrev(u);
    ll R = getNext(u);
    DIST -= dist(L, u) + dist(u, R) - dist(L, R);
    st.erase(in[u]);
}

ll L = 1 , R = 0 ;

void MO(ll i)
{
    while (L > Q[i].l) add(--L);
    while (R < Q[i].r) add(++R);
    while (L < Q[i].l) del(L++);
    while (R > Q[i].r) del(R--);
}
bool check = 1 ;

ll t[4 * N] , t2[4 * N] ;
void build(ll id , ll l , ll r)
{
        if(l == r)
        {
            t[id] = t2[id] = c[l] ;
            return ;
        }
        ll mid = l + (r - l) / 2;
        build(id * 2 , l , mid) ;
        build(id * 2 + 1 , mid + 1 , r) ;
        t[id] = max(t[id * 2] , t[id * 2 + 1]) ;
        t2[id] = min(t2[id * 2] , t2[id * 2 + 1]) ;
}
ll getmax(ll id , ll l , ll r , ll u , ll v)
{
        if(u > r || l > v) return -1 ;
        if(u <= l && r <= v) return t[id] ;
        ll mid = l + (r - l) / 2 ;
        return max(getmax(id * 2 , l , mid , u , v) , getmax(id * 2 + 1 , mid + 1 , r ,  u , v)) ;
}
ll getmin(ll id , ll l , ll r , ll u , ll v)
{
        if(u > r || l > v) return 1e9 ;
        if(u <= l && r <= v) return t2[id] ;
        ll mid = l + (r - l) / 2 ;
    return min(getmin(id * 2 , l , mid , u , v) , getmin(id * 2 + 1 , mid + 1 , r ,  u , v)) ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    if(fopen(name".inp" , "r"))
    {
        freopen(name".inp" , "r" , stdin);
        freopen(name".out" , "w" , stdout);
    }

    cin >> n >> m >> q ;
    S = sqrt(m) + 1 ;

    FOR(i ,1 , n - 1)
    {
        ll x , y ;
        cin >> x >> y ;
        if(x > y) swap(x , y) ;
        if(x != i || y != i + 1) check = 0 ;
        a[x].pb(y);
        a[y].pb(x);

    }

    dfs(1 , 0);

    FOR(i ,1 , n) id[in[i]] = i;

    FOR(j ,1 , LOG)
        FOR(i ,1 , n)
            par[i][j] = par[par[i][j - 1]][j - 1];

    FOR(i ,1 , m) cin >> c[i];

    if(check)
    {

        build(1 , 1 , m) ;

        FOR(i ,1, q)
        {
            ll l , r ;
            cin >> l >> r ;
            cout << getmax(1 ,1 , m , l , r) - getmin(1 , 1, m , l , r) + 1 <<'\n';
        }
        return 0 ;
    }
    FOR(i ,1 , q)
    {
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }

    sort(Q + 1 , Q + q + 1 , cmp);

    DIST = 0;
    st.clear();
    memset(cntNode , 0 , sizeof(cntNode));
    L = 1; R = 0;

    FOR(i ,1 , q)
    {
        MO(i);
        ANS[Q[i].id] = DIST / 2 + 1;
    }

    FOR(i ,1 , q) cout << ANS[i] << '\n';

    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(name".inp" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(name".out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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