Submission #1301477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301477		sitingfake	Tourism (JOI23_tourism)	C++20	0 / 100	92 ms	18416 KiB

tourism

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ii pair <int , int>
#define iii pair <int , ii>
#define se second
#define fi first
#define all(v) (v).begin() , (v).end()
#define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
#define bit(x,i) (((x) >> (i)) & 1LL)
#define flip(x,i) ((x) ^ (1LL << (i)))
#define ms(d,x) memset(d , x , sizeof(d))
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right
#define prev __prev
#define next __next
#define sitingfake 1
#define orz 1
//constant

const long long mod = 1e9 + 7;
const long long linf = 4557430888798830399LL;
const long long nlinf = -4485090715960753727LL;
const int LOG = 20;
const int inf = 1061109567;
const int ninf = -1044266559;
const int dx[] = {0 , -1 , 0 , 1};
const int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a < 0) a += mod;
    a %= mod;
    return;
}

void Mul(ll & a, ll b)
{
    (a *= (b % mod)) %= mod;
    return;
}

//code
const int maxn = 1e5 + 7;

struct Bitset
{
    #define ull unsigned long long
    #define MAX_BIT_ON(x) (63 - __builtin_clzll(x))
    #define MIN_BIT_ON(x) (__builtin_ctzll(x))
    // 50000 -> O(1) , 100000 -> O(log BIT)

    const int LIM = 1e5;
    ull group[1605];
    ull GroupOnline[50];
    ull MAX = 18446744073709551615ULL;
    ull mask[66];

    int SIZE = 0;
    int numGroup;
    int numOfnumGroup;

    void init(int sz)
    {
        SIZE = sz;
        numGroup = (SIZE / 64) + 1;
        numOfnumGroup = (SIZE / (64 * 64)) + 1;
        mask[0] = 1;
        mask[64] = MAX;
        for(int i = 1; i <= 63; i++)
        {
            mask[i] = mask[i - 1] * 2ULL;
        }
        for(int i = 0; i <= 63; i++)
        {
            mask[i]--;
        }
        ms(group , 0);
        ms(GroupOnline , 0);
    }

    void setOn(int x)
    {
        int id = x >> 6;
        int b;
        if(GroupOnline[id >> 6] == 0)
        {
            b = id & 63;
            GroupOnline[id >> 6] |= (1ULL << b);
        }
        b = x & 63;
        group[id] |= (1ULL << b);
    }

    void setOff(int x)
    {
        int id = x >> 6;
        int b = x & 63;
        group[id] &= (~(1ULL << b));
        if(group[id] == 0)
        {
            b = id & 63;
            GroupOnline[id >> 6] &= (~(1ULL << b));
        }
    }

    int lower(int val)
    {
        int id = val >> 6;
        ll curpos = val & 63;
        ull tmp = group[id] & mask[curpos];
        if(curpos && tmp > 0)
        {
            return val - curpos + MAX_BIT_ON(tmp);
        }
        else
        {
            int Groupid = id >> 6;
            ll pos = Groupid & 63;
            ull tmp1 = GroupOnline[Groupid] & mask[pos];
            if(pos && tmp1 > 0)
            {
                int maskPos = Groupid - pos + MAX_BIT_ON(tmp1);
                return (maskPos << 6) + MAX_BIT_ON(group[maskPos]);
            }
            else
            {
                for(int i = Groupid - 1; i >= 0; i--)
                {
                    if(GroupOnline[i] > 0)
                    {
                        int maskPos = ((i << 6) + MAX_BIT_ON(GroupOnline[i]));
                        return (maskPos << 6) + MAX_BIT_ON(group[maskPos]);
                    }
                }
            }
        }
        return -1;
    }

    int upper(int val)
    {
        int id = val >> 6;
        ll curpos = val & 63;
        ull tmp = group[id] & (MAX ^ mask[curpos + 1]);
        if(curpos && tmp > 0)
        {
            return val - curpos + MIN_BIT_ON(tmp);
        }
        else
        {
            int idGroup = id >> 6;
            int pos = idGroup & 63;

            ull tmp1 = GroupOnline[idGroup] & (MAX ^ mask[curpos + 1]);
            if(pos && tmp1)
            {
                int maskPos = idGroup - pos + MIN_BIT_ON(tmp1);
                return (maskPos << 6) + MIN_BIT_ON(group[maskPos]);
            }
            else
            {
                for(int i = idGroup + 1; i <= numOfnumGroup; i++)
                {
                    if(GroupOnline[i])
                    {
                        int maskPos = (i << 6) + MIN_BIT_ON(GroupOnline[i]);
                        return (maskPos << 6) + MIN_BIT_ON(group[maskPos]);
                    }
                }
            }
        }
        return -1;
    }
}B;

int n , m , q;

int BlockSize = 0;

int c[maxn] , curNodes , cnt[maxn];
int id[maxn];

struct Query
{
    int l , r;
    int id;
    bool operator < (Query &other)
    {
        if((l / BlockSize) == (other.l / BlockSize))
        {
            return r < other.r;
        }
        return l < other.l;
    }
}Q[maxn];

int ans[maxn] , sumDist;

vector <int> adj[maxn];
int in[maxn] , out[maxn] , depth[maxn] ,timer;
int arr[maxn * 2][20];
int tin[maxn] , tout[maxn] , timer2;
void dfs(int u , int p)
{
    in[u] = ++timer;
    tin[u] = ++timer2;
    arr[timer][0] = u;
    for(int v : adj[u])
    {
        if(v != p)
        {
            depth[v] = depth[u] + 1;
            dfs(v , u);
            arr[++timer][0] = u;
        }
    }
    out[u] = timer;
    tout[u] = timer2;
}

void BuildLca()
{
    for(int j = 1; (1 << j) <= timer ; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= timer ; i++)
        {
            arr[i][j] = (depth[arr[i][j - 1]] < depth[arr[i + (1 << (j - 1))][j - 1]])
            ? arr[i][j - 1] : arr[i + (1 << (j - 1))][j - 1];
        }
    }
}

int lca(int u , int v)
{
    int l = in[u] , r = in[v];
    if(l > r) swap(l , r);
    int k = __lg(r - l + 1);
    if(depth[arr[l][k]] < depth[arr[r - (1 << k) + 1][k]])
    {
        return arr[l][k];
    }
    return arr[r - (1 << k) + 1][k];
}

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

void AddSet(int u)
{
    if(curNodes == 1)
    {
        B.setOn(u);
        return;
    }

    int l = B.lower(u);

    if(l == -1)
    {
        if(cnt[n] != 0)
        {
            l = n;
        }
        else l = B.lower(n);
    }

    int r = B.upper(u);

    if(r == -1)
    {
        if(cnt[1] != 0)
        {
            r = 1;
        }
        else r = B.upper(1);
    }
    assert(l != -1);
    assert(r != -1);
    sumDist -= dist(id[l] , id[r]);
    sumDist += dist(id[l] , id[u]);
    sumDist += dist(id[u] , id[r]);
    B.setOn(u);
}

void DelSet(int u)
{
    if(curNodes <= 1)
    {
        sumDist = 0;
        B.setOff(u);
        return;
    }
    B.setOff(u);
    int l = B.lower(u);
    if(l == -1)
    {
        if(cnt[n]) l = n;
        else l = B.lower(n);
    }
    int r = B.upper(u);
    if(r == -1)
    {
        if(cnt[1]) r = 1;
        else r = B.upper(1);
    }
    assert(l != -1);
    assert(r != -1);

    sumDist -= dist(id[l] , id[u]);
    sumDist -= dist(id[r] , id[u]);
    sumDist += dist(id[l] , id[r]);
}

void add_Node(int u)
{
    //cout << id[u] << endl;
    if(cnt[u] == 0)
    {
        curNodes++;
        AddSet(u);
    }
    cnt[u]++;
}

void del_Node(int u)
{
    if(cnt[u] == 1)
    {
        curNodes--;
        DelSet(u);
    }
    cnt[u]--;
}


int L = 1 , R = 0;

void Mo(const int & l, const int & r)
{
    while(R < r){++R;add_Node(tin[c[R]]);}
    while(L > l){--L;add_Node(tin[c[L]]);}
    while(L < l){del_Node(tin[c[L]]);++L;}
    while(R > r){del_Node(tin[c[R]]);--R;}
}
void solve(void)
{
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++)
    {
        int u , v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> c[i];
    }
    for(int i = 1; i <= q; i++)
    {
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    dfs(1 , -1);
    BuildLca();
    B.init(n + 2);
    for(int i = 1; i <= n; i++)
    {
        id[tin[i]] = i;
    }
    BlockSize = sqrt(m) + 1;
    sort(Q + 1 , Q + q + 1);
    for(int i = 1; i <= q; i++)
    {
        Mo(Q[i].l , Q[i].r);
        ans[Q[i].id] = (sumDist / 2) + 1;
    }
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << "\n";
    }
}
/**
7 6 1
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
4 6
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

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

   int tc = 1;
//   cin >> tc;
   while(tc--) solve();

//   execute;
}

Compilation message (stderr)

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

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