Submission #1261194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261194		Zbyszek99	Tourism (JOI23_tourism)	C++20	100 / 100	1347 ms	35284 KiB

tourism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int tree_siz = 1024*256-1;
int drzewo[tree_siz+1];

int get_sum(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return 0;
    if(p1 >= s1 && p2 <= s2) return drzewo[akt];
    return get_sum(akt*2,p1,(p1+p2)/2,s1,s2)+get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}

void upd(int v)
{
    drzewo[v] = drzewo[v*2]+drzewo[v*2+1];
    if(v != 1) upd(v/2);
}

void change(int ind, int w)
{
    drzewo[tree_siz/2+ind+1] += w;
    upd((tree_siz/2+ind+1)/2);
}

struct query
{
    int l,r,ind;
    bool operator<(const query& other)
    {
        return l < other.l;
    }
};

struct event
{
    int l,r,k;
    bool operator<(const event& other)
    {
        return l < other.l;
    }
};

vi graph[100001];
int depth[100001];
int max_pre[100001];
int pre[100001];
int jump[100001][18];
int query_ans[100001];
int cur_pre = 0;
int first_L[100001];
int first_R[100001];

int lcaf(int a, int b)
{
    if(pre[b] >= pre[a] && pre[b] <= max_pre[a]) return a;
    for(int bit = 17; bit >= 0; bit--)
    {
        int l2 = jump[a][bit];
        if(!(pre[b] >= pre[l2] && pre[b] <= max_pre[l2])) a = l2;
    }
    return jump[a][0];
}

void dfs(int v, int pop)
{
    jump[v][0] = pop;
    depth[v] = depth[pop]+1;
    pre[v] = cur_pre++;
    max_pre[v] = pre[v];
    forall(it,graph[v])
    {
        if(it != pop) 
        {
            dfs(it,v);
            max_pre[v] = max_pre[it];
        }
    }
}

vector<pii> gen_tree(vi s)
{
    vector<pii> v2;
    forall(it,s) v2.pb({pre[it],it});
    sort(all(v2));
    set<pii> tr;
    forall(it,v2) tr.insert(it);
    rep(i,siz(v2))
    {
        int l = lcaf(v2[i].ss,v2[(i+1)%siz(v2)].ss);
        tr.insert({pre[l],l});
    }
    vector<pii> ans;
    vi v;
    forall(it,tr) v.pb(it.ss);
    rep(i,siz(v)-1)
    {
        ans.pb({lcaf(v[i],v[i+1]),v[i+1]});
    }
    return ans;
}

vector<event> events;

pii dfs_solve(int v, int pop)
{
    int L = first_L[v];
    int R = first_R[v];
    forall(it,graph[v])
    {
        if(it != pop)
        {
            pii d = dfs_solve(it,v);
            events.pb({d.ff,d.ss,depth[it]+depth[v]-2*depth[lcaf(it,v)]});
            if(d.ss != 1e9)
            {
                change(d.ss,depth[it]+depth[v]-2*depth[lcaf(it,v)]);
            }
            L = max(L,d.ff);
            R = min(R,d.ss);
        }
    }
    return {L,R};
}

void solve(vi c, vector<query> q)
{   
    if(siz(q) == 0) return;
    if(siz(c) <= 1)
    {
        forall(it,q) query_ans[it.ind] = 1;
        return;
    }
    int mid = siz(c)/2;
    vector<pii> tr = gen_tree(c);
    forall(it,tr)
    {
        graph[it.ff].pb(it.ss);
        graph[it.ss].pb(it.ff);
        first_L[it.ff] = -1;
        first_R[it.ff] = 1e9;
        first_L[it.ss] = -1;
        first_R[it.ss] = 1e9;
    }
    rep(i,siz(c))
    {
        if(i < mid)
        {
            first_L[c[i]] = max(first_L[c[i]],i);
        }
        else
        {
            first_R[c[i]] = min(first_R[c[i]],i);
        }
    
    }
    events = {};
    dfs_solve(c[mid],c[mid]);
    forall(it,tr)
    {
        graph[it.ff] = {};
        graph[it.ss] = {};
    }
    vi l;
    vi r;
    vector<query> lq;
    vector<query> rq;
    vector<query> my_q;
    rep(i,mid)
    {
        l.pb(c[i]);
    }
    rep2(i,mid+1,siz(c)-1)
    {
        r.pb(c[i]);
    }
    forall(it,q)
    {
        if(it.r < mid) lq.pb(it);
        else if(it.l > mid)
        {
            rq.pb({it.l-mid-1,it.r-mid-1,it.ind});
        }
        else my_q.pb(it);
    }
    sort(all(my_q));
    reverse(all(my_q));
    int cur_e = 0;
    sort(all(events));
    reverse(all(events));
    int sum = 0;
    forall(it,my_q)
    {
        while(cur_e < siz(events) && events[cur_e].l >= it.l)
        {
            sum += events[cur_e].k;
            if(events[cur_e].r != 1e9)
            {
                change(events[cur_e].r,-events[cur_e].k);
            }
            cur_e++;
        }
        query_ans[it.ind] = sum+get_sum(1,0,tree_siz/2,mid,it.r)+1;
    }
    rep2(i,cur_e,siz(events)-1)
    {
        if(events[i].r != 1e9)
        {
            change(events[i].r,-events[i].k);
        }
    }
    solve(l,lq);
    solve(r,rq);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m,q;
    cin >> n >> m >> q;
    rep(i,n-1)
    {
        int a,b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    dfs(1,1);
    rep2(bit,1,17)
    {
        rep2(i,1,n)
        {
            jump[i][bit] = jump[jump[i][bit-1]][bit-1];
        }
    }
    rep2(i,1,n) graph[i] = {};
    vi C(m);
    rep(i,m) cin >> C[i];
    vector<query> queries;
    rep(qq,q)
    {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        queries.pb({l,r,qq});
    }
    solve(C,queries);
    rep(qq,q)
    {
        cout << query_ans[qq] << "\n";
    }
}

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