oj.uz

Submission #949684

# Submission time Handle Problem Language Result Execution time Memory
949684 2024-03-19T15:13:07 Z andrei_boaca Tourism (JOI23_tourism) C++17
5 / 100
 717 ms 51260 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;
                    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;
                    }
                }
                sol[ind]=cnt-nivmin;
            }
        }
    for(int i=1;i<=q;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29272 KB Output is correct
2 Correct 4 ms 29276 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 7 ms 29356 KB Output is correct
5 Correct 6 ms 27272 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 8 ms 47964 KB Output is correct
9 Correct 11 ms 47708 KB Output is correct
10 Correct 9 ms 35420 KB Output is correct
11 Correct 10 ms 37468 KB Output is correct
12 Correct 19 ms 37468 KB Output is correct
13 Correct 15 ms 37656 KB Output is correct
14 Correct 15 ms 35620 KB Output is correct
15 Correct 9 ms 37468 KB Output is correct
16 Correct 9 ms 35628 KB Output is correct
17 Correct 10 ms 37672 KB Output is correct
18 Correct 10 ms 35616 KB Output is correct
19 Correct 10 ms 33628 KB Output is correct
20 Correct 10 ms 33420 KB Output is correct
21 Correct 11 ms 33584 KB Output is correct
22 Correct 9 ms 33372 KB Output is correct
23 Correct 9 ms 33588 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 10 ms 17244 KB Output is correct
26 Correct 7 ms 17240 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 15196 KB Output is correct
29 Correct 4 ms 17252 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29272 KB Output is correct
2 Correct 4 ms 29276 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 7 ms 29356 KB Output is correct
5 Correct 6 ms 27272 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 8 ms 47964 KB Output is correct
9 Correct 11 ms 47708 KB Output is correct
10 Correct 9 ms 35420 KB Output is correct
11 Correct 10 ms 37468 KB Output is correct
12 Correct 19 ms 37468 KB Output is correct
13 Correct 15 ms 37656 KB Output is correct
14 Correct 15 ms 35620 KB Output is correct
15 Correct 9 ms 37468 KB Output is correct
16 Correct 9 ms 35628 KB Output is correct
17 Correct 10 ms 37672 KB Output is correct
18 Correct 10 ms 35616 KB Output is correct
19 Correct 10 ms 33628 KB Output is correct
20 Correct 10 ms 33420 KB Output is correct
21 Correct 11 ms 33584 KB Output is correct
22 Correct 9 ms 33372 KB Output is correct
23 Correct 9 ms 33588 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 10 ms 17244 KB Output is correct
26 Correct 7 ms 17240 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 15196 KB Output is correct
29 Correct 4 ms 17252 KB Output is correct
30 Correct 142 ms 15448 KB Output is correct
31 Correct 218 ms 21600 KB Output is correct
32 Correct 281 ms 21984 KB Output is correct
33 Correct 260 ms 23756 KB Output is correct
34 Correct 300 ms 25688 KB Output is correct
35 Correct 705 ms 29808 KB Output is correct
36 Correct 707 ms 25760 KB Output is correct
37 Correct 717 ms 25768 KB Output is correct
38 Correct 263 ms 47960 KB Output is correct
39 Correct 245 ms 48108 KB Output is correct
40 Correct 242 ms 47964 KB Output is correct
41 Correct 681 ms 48116 KB Output is correct
42 Correct 673 ms 48120 KB Output is correct
43 Correct 673 ms 48088 KB Output is correct
44 Correct 244 ms 47960 KB Output is correct
45 Correct 268 ms 48052 KB Output is correct
46 Correct 257 ms 47960 KB Output is correct
47 Correct 696 ms 48052 KB Output is correct
48 Correct 679 ms 48028 KB Output is correct
49 Correct 690 ms 48048 KB Output is correct
50 Correct 252 ms 47960 KB Output is correct
51 Correct 259 ms 48264 KB Output is correct
52 Correct 258 ms 48024 KB Output is correct
53 Correct 253 ms 47964 KB Output is correct
54 Correct 261 ms 48032 KB Output is correct
55 Correct 255 ms 48012 KB Output is correct
56 Incorrect 8 ms 47704 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47708 KB Output is correct
2 Correct 6 ms 47828 KB Output is correct
3 Incorrect 8 ms 47960 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 47708 KB Output is correct
2 Correct 38 ms 49776 KB Output is correct
3 Incorrect 43 ms 51260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29272 KB Output is correct
2 Correct 4 ms 29276 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 7 ms 29356 KB Output is correct
5 Correct 6 ms 27272 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 8 ms 47964 KB Output is correct
9 Correct 11 ms 47708 KB Output is correct
10 Correct 9 ms 35420 KB Output is correct
11 Correct 10 ms 37468 KB Output is correct
12 Correct 19 ms 37468 KB Output is correct
13 Correct 15 ms 37656 KB Output is correct
14 Correct 15 ms 35620 KB Output is correct
15 Correct 9 ms 37468 KB Output is correct
16 Correct 9 ms 35628 KB Output is correct
17 Correct 10 ms 37672 KB Output is correct
18 Correct 10 ms 35616 KB Output is correct
19 Correct 10 ms 33628 KB Output is correct
20 Correct 10 ms 33420 KB Output is correct
21 Correct 11 ms 33584 KB Output is correct
22 Correct 9 ms 33372 KB Output is correct
23 Correct 9 ms 33588 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 10 ms 17244 KB Output is correct
26 Correct 7 ms 17240 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 15196 KB Output is correct
29 Correct 4 ms 17252 KB Output is correct
30 Correct 142 ms 15448 KB Output is correct
31 Correct 218 ms 21600 KB Output is correct
32 Correct 281 ms 21984 KB Output is correct
33 Correct 260 ms 23756 KB Output is correct
34 Correct 300 ms 25688 KB Output is correct
35 Correct 705 ms 29808 KB Output is correct
36 Correct 707 ms 25760 KB Output is correct
37 Correct 717 ms 25768 KB Output is correct
38 Correct 263 ms 47960 KB Output is correct
39 Correct 245 ms 48108 KB Output is correct
40 Correct 242 ms 47964 KB Output is correct
41 Correct 681 ms 48116 KB Output is correct
42 Correct 673 ms 48120 KB Output is correct
43 Correct 673 ms 48088 KB Output is correct
44 Correct 244 ms 47960 KB Output is correct
45 Correct 268 ms 48052 KB Output is correct
46 Correct 257 ms 47960 KB Output is correct
47 Correct 696 ms 48052 KB Output is correct
48 Correct 679 ms 48028 KB Output is correct
49 Correct 690 ms 48048 KB Output is correct
50 Correct 252 ms 47960 KB Output is correct
51 Correct 259 ms 48264 KB Output is correct
52 Correct 258 ms 48024 KB Output is correct
53 Correct 253 ms 47964 KB Output is correct
54 Correct 261 ms 48032 KB Output is correct
55 Correct 255 ms 48012 KB Output is correct
56 Incorrect 8 ms 47704 KB Output isn't correct
57 Halted 0 ms 0 KB -