Submission #949816

#	Time	Username	Problem	Language	Result	Execution time	Memory
949816		andrei_boaca	Tourism (JOI23_tourism)	C++17	100 / 100	672 ms	112192 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,m,q,v[100005],niv[100005],par[100005],timp,in[100005],out[100005],sol[100005],lin[100005];
int dp[21][100005];
vector<int> muchii[100005];
vector<pii> qr[100005];
int rmax[21][100005],rmin[21][100005];
int loga[100005];
struct date
{
    int l,r,add;
};
vector<date> events[100005];
vector<int> poz[100005];
set<pii> s[100005];
set<pair<pii,int>> s1[100005];
void dfs(int nod)
{
    timp++;
    lin[timp]=nod;
    in[nod]=timp;
    dp[0][nod]=par[nod];
    for(int i=1;i<=20;i++)
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    int who=0,maxim=0;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
            if(s[i].size()>=maxim)
            {
                maxim=s[i].size();
                who=i;
            }
        }
    out[nod]=timp;
    if(who==0)
    {
        s1[nod].insert({{1,m},niv[nod]});
        for(int i:poz[nod])
        {
            s[nod].insert({i,i});
            auto it=prev(s1[nod].lower_bound({{i+1,0},0}));
            int l=(*it).first.first;
            int r=(*it).first.second;
            int l1=l;
            int r1=i-1;
            int l2=i+1;
            int r2=r;
            s1[nod].erase(it);
            if(l1<=r1)
                s1[nod].insert({{l1,r1},niv[nod]});
            if(l2<=r2)
                s1[nod].insert({{l2,r2},niv[nod]});
        }
        return;
    }
    swap(s[nod],s[who]);
    swap(s1[nod],s1[who]);
    for(int i:muchii[nod])
        if(i!=par[nod])
            if(i!=who)
            {
                for(pii j:s[i])
                {
                    s[nod].insert(j);
                    int st=j.first;
                    int dr=j.second;
                    auto it=prev(s1[nod].lower_bound({{st+1,0},0}));
                    int l=(*it).first.first;
                    int r=(*it).first.second;
                    int x=(*it).second;
                    int l1=l;
                    int r1=st-1;
                    int l2=dr+1;
                    int r2=r;
                    s1[nod].erase(it);
                    events[l].push_back({l,r,x-niv[nod]});
                    events[r+1].push_back({l,r,niv[nod]-x});
                    if(l1<=r1)
                        s1[nod].insert({{l1,r1},niv[nod]});
                    if(l2<=r2)
                        s1[nod].insert({{l2,r2},niv[nod]});
                }
                for(auto j:s1[i])
                {
                    int l=j.first.first;
                    int r=j.first.second;
                    int x=j.second;
                    events[l].push_back({l,r,x-niv[nod]});
                    events[r+1].push_back({l,r,niv[nod]-x});
                }
                s1[i].clear();
                s[i].clear();
            }
    for(int i:poz[nod])
    {
        s[nod].insert({i,i});
        auto it=prev(s1[nod].lower_bound({{i+1,0},0}));
        int l=(*it).first.first;
        int r=(*it).first.second;
        int x=(*it).second;
        int l1=l;
        int r1=i-1;
        int l2=i+1;
        int r2=r;
        s1[nod].erase(it);
        events[l].push_back({l,r,x-niv[nod]});
        events[r+1].push_back({l,r,niv[nod]-x});
        if(l1<=r1)
            s1[nod].insert({{l1,r1},niv[nod]});
        if(l2<=r2)
            s1[nod].insert({{l2,r2},niv[nod]});
    }
}
int aib[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=m;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int getmin(int l,int r)
{
    int lg=loga[r-l+1];
    return min(rmin[lg][l],rmin[lg][r-(1<<lg)+1]);
}
int getmax(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmax[lg][l],rmax[lg][r-(1<<lg)+1]);
}
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=17;i>=0;i--)
        if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return par[a];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>v[i];
        poz[v[i]].push_back(i);
    }
    dfs(1);
    for(auto i:s1[1])
    {
        int l=i.first.first;
        int r=i.first.second;
        int x=i.second+1;
        events[l].push_back({l,r,x});
        events[r+1].push_back({l,r,x});
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        qr[l].push_back({r,i});
    }
    for(int i=1;i<=m;i++)
    {
        for(int bit=0;bit<20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int i=1;i<=m;i++)
    {
        v[i]=in[v[i]];
        rmax[0][i]=v[i];
        rmin[0][i]=v[i];
    }
    for(int j=1;j<=17;j++)
        for(int i=1;i<=m;i++)
        {
            rmax[j][i]=rmax[j-1][i];
            rmin[j][i]=rmin[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=m)
            {
                rmax[j][i]=max(rmax[j][i],rmax[j-1][poz]);
                rmin[j][i]=min(rmin[j][i],rmin[j-1][poz]);
            }
        }
    for(int i=1;i<=m;i++)
    {
        for(date j:events[i])
        {
            update(j.l,j.add);
            update(j.r+1,-j.add);
        }
        for(pii p:qr[i])
        {
            int poz=p.first,ind=p.second;
            int val=suma(poz);
            val=n-val;
            int a=getmin(i,poz);
            int b=getmax(i,poz);
            a=lin[a];
            b=lin[b];
            int lca=LCA(a,b);
            val-=niv[lca];
            sol[ind]=val;
        }
    }
    for(int i=1;i<=q;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'void dfs(int)':
tourism.cpp:34:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             if(s[i].size()>=maxim)
      |                ~~~~~~~~~~~^~~~~~~

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