Submission #949741

#	Time	Username	Problem	Language	Result	Execution time	Memory
949741		andrei_boaca	Tourism (JOI23_tourism)	C++17	28 / 100	5090 ms	60844 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int bucksize=500;
int n,m,q,c[100005],niv[100005],in[100005],out[100005],lin[500005],rmq[21][500005],loga[500005],timp,par[100005];
int sol[100005],nivmin,cnt;
set<pii> s;
vector<int> muchii[100005];
void dfs(int nod)
{
    timp++;
    lin[timp]=nod;
    in[nod]=timp;
    bool have=0;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
            timp++;
            lin[timp]=nod;
            have=1;
        }
    if(!have)
    {
        timp++;
        lin[timp]=nod;
    }
    out[nod]=timp;
}
struct date
{
    int l,r,ind;
};
int getbuck(int x)
{
    return x/bucksize+(x%bucksize!=0);
}
bool byr(date a, date b)
{
    return a.r<b.r;
}
vector<date> qr[100005];
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int getmin(int l,int r)
{
    int lg=loga[r-l+1];
    int a=rmq[lg][r-(1<<lg)+1];
    int b=rmq[lg][l];
    if(niv[a]<niv[b])
        return a;
    return b;
}
int LCA(int a,int b)
{
    if(in[a]>in[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    int l=out[a];
    int r=in[b];
    return getmin(l,r);
}
void addnode(int nod)
{
    if(s.find({in[nod],nod})!=s.end())
        return;
    s.insert({in[nod],nod});
    if(s.size()==1)
    {
        nivmin=niv[nod];
        cnt=nivmin+1;
        return;
    }
    int nmin=1e9;
    int nmax=0;
    auto it=s.find({in[nod],nod});
    bool have=0;
    if(it!=s.begin())
    {
        int st=(*prev(it)).second;
        int x=LCA(st,nod);
        nmin=min(nmin,niv[x]);
        nmax=max(nmax,niv[x]);
    }
    it++;
    if(it!=s.end())
    {
        int dr=(*it).second;
        if(isancestor(nod,dr))
            have=1;
        int x=LCA(nod,dr);
        nmin=min(nmin,niv[x]);
        nmax=max(nmax,niv[x]);
    }
    if(nivmin>nmin)
    {
        if(!have)
            cnt+=niv[nod]-nmin;
        nivmin=min(nivmin,nmin);
    }
    else
    {
        if(!have)
            cnt+=niv[nod]-nmax;
    }
}
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>>c[i];
    dfs(1);
    for(int i=1;i<=timp;i++)
    {
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int i=1;i<=timp;i++)
        rmq[0][i]=lin[i];
    for(int j=1;j<=20;j++)
        for(int i=1;i<=timp;i++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=timp&&niv[rmq[j-1][poz]]<niv[rmq[j][i]])
                rmq[j][i]=rmq[j-1][poz];
        }
    int bmax=0;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        int b=getbuck(l);
        bmax=max(bmax,b);
        qr[b].push_back({l,r,i});
    }
    for(int b=1;b<=bmax;b++)
        if(!qr[b].empty())
        {
            sort(qr[b].begin(),qr[b].end(),byr);
            reverse(qr[b].begin(),qr[b].end());
            while(!qr[b].empty()&&getbuck(qr[b].back().r)==b)
            {
                int l=qr[b].back().l;
                int r=qr[b].back().r;
                int ind=qr[b].back().ind;
                qr[b].pop_back();
                s.clear();
                nivmin=niv[c[l]];
                cnt=nivmin+1;
                s.insert({in[c[l]],c[l]});
                for(int i=l+1;i<=r;i++)
                {
                    int nod=c[i];
                    addnode(nod);
                }
                sol[ind]=cnt-nivmin;
            }
            s.clear();
            int poz=b*bucksize;
            cnt=0;
            nivmin=0;
            while(!qr[b].empty())
            {
                int l=qr[b].back().l;
                int r=qr[b].back().r;
                int ind=qr[b].back().ind;
                qr[b].pop_back();
                while(poz<r)
                {
                    poz++;
                    int nod=c[poz];
                    addnode(nod);
                }
                int last=b*bucksize;
                int auxniv=nivmin;
                int auxcnt=cnt;
                vector<pii> toerase;
                assert(last-l+1<=bucksize);
                for(int i=l;i<=last;i++)
                {
                    int nod=c[i];
                    if(s.find({in[nod],nod})!=s.end())
                        continue;
                    toerase.push_back({in[nod],nod});
                    addnode(nod);
                }
                sol[ind]=cnt-nivmin;
                for(pii p:toerase)
                    s.erase(p);
                nivmin=auxniv;
                cnt=auxcnt;
            }
        }
    for(int i=1;i<=q;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

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