oj.uz

Submission #949674

# Submission time Handle Problem Language Result Execution time Memory
949674 2024-03-19T15:07:29 Z andrei_boaca Tourism (JOI23_tourism) C++17
0 / 100
 47 ms 50516 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int bucksize=320;
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];
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);
}
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<=18;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];
        }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        int b=getbuck(l);
        qr[b].push_back({l,r,i});
    }
    for(int b=1;(b-1)*bucksize+1<=n;b++)
        if(!qr[b].empty())
        {
            sort(qr[b].begin(),qr[b].end(),byr);
            reverse(qr[b].begin(),qr[b].end());
            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();
                set<pii> s;
                int nivmin=niv[c[l]];
                int cnt=nivmin+1;
                s.insert({in[c[l]],c[l]});
                for(int i=l+1;i<=r;i++)
                {
                    int nod=c[i];
                    if(s.find({in[nod],nod})!=s.end())
                        continue;
                    //cnt++;
                    s.insert({in[nod],nod});
                    int nmin=1e9;
                    auto it=s.find({in[nod],nod});
                    bool have=0;
                    if(it!=s.begin())
                    {
                        int st=(*prev(it)).second;
                        /*if(isancestor(nod,st))
                            have=1;*/
                        int x=LCA(st,nod);
                        nmin=min(nmin,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]);
                    }
                    if(nmin<nivmin)
                    {
                        if(!have)
                            cnt+=niv[nod]-nmin;
                        nivmin=nmin;
                    }
                    else
                    {
                        if(!have)
                            cnt+=niv[nod]-nmin;
                    }
                }
                sol[ind]=cnt-nivmin;
            }
        }
    for(int i=1;i<=q;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 6 ms 47708 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Incorrect 9 ms 47708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 6 ms 47708 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Incorrect 9 ms 47708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47704 KB Output is correct
2 Correct 6 ms 47708 KB Output is correct
3 Incorrect 9 ms 47708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47828 KB Output is correct
2 Incorrect 47 ms 50516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47832 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Incorrect 11 ms 47708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 6 ms 47708 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Incorrect 9 ms 47708 KB Output isn't correct
5 Halted 0 ms 0 KB -