oj.uz

Submission #949697

# Submission time Handle Problem Language Result Execution time Memory
949697 2024-03-19T15:18:17 Z andrei_boaca Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 56532 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<=m;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++)
    {
        assert(sol[i]!=0);
        cout<<sol[i]<<'\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.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 Correct 6 ms 47708 KB Output is correct
4 Correct 9 ms 47824 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47792 KB Output is correct
8 Correct 8 ms 47708 KB Output is correct
9 Correct 10 ms 47708 KB Output is correct
10 Correct 10 ms 47708 KB Output is correct
11 Correct 10 ms 47796 KB Output is correct
12 Correct 17 ms 47704 KB Output is correct
13 Correct 16 ms 47708 KB Output is correct
14 Correct 19 ms 47704 KB Output is correct
15 Correct 11 ms 47708 KB Output is correct
16 Correct 10 ms 47708 KB Output is correct
17 Correct 10 ms 47708 KB Output is correct
18 Correct 10 ms 47708 KB Output is correct
19 Correct 10 ms 47708 KB Output is correct
20 Correct 10 ms 47708 KB Output is correct
21 Correct 10 ms 47708 KB Output is correct
22 Correct 10 ms 47864 KB Output is correct
23 Correct 10 ms 47704 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 11 ms 47796 KB Output is correct
26 Correct 11 ms 47704 KB Output is correct
27 Correct 7 ms 47844 KB Output is correct
28 Correct 6 ms 47708 KB Output is correct
29 Correct 6 ms 47704 KB Output is correct

Subtask #2
5.0 / 5.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 Correct 6 ms 47708 KB Output is correct
4 Correct 9 ms 47824 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47792 KB Output is correct
8 Correct 8 ms 47708 KB Output is correct
9 Correct 10 ms 47708 KB Output is correct
10 Correct 10 ms 47708 KB Output is correct
11 Correct 10 ms 47796 KB Output is correct
12 Correct 17 ms 47704 KB Output is correct
13 Correct 16 ms 47708 KB Output is correct
14 Correct 19 ms 47704 KB Output is correct
15 Correct 11 ms 47708 KB Output is correct
16 Correct 10 ms 47708 KB Output is correct
17 Correct 10 ms 47708 KB Output is correct
18 Correct 10 ms 47708 KB Output is correct
19 Correct 10 ms 47708 KB Output is correct
20 Correct 10 ms 47708 KB Output is correct
21 Correct 10 ms 47708 KB Output is correct
22 Correct 10 ms 47864 KB Output is correct
23 Correct 10 ms 47704 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 11 ms 47796 KB Output is correct
26 Correct 11 ms 47704 KB Output is correct
27 Correct 7 ms 47844 KB Output is correct
28 Correct 6 ms 47708 KB Output is correct
29 Correct 6 ms 47704 KB Output is correct
30 Correct 128 ms 47708 KB Output is correct
31 Correct 181 ms 48192 KB Output is correct
32 Correct 261 ms 47964 KB Output is correct
33 Correct 271 ms 47988 KB Output is correct
34 Correct 260 ms 47984 KB Output is correct
35 Correct 709 ms 47972 KB Output is correct
36 Correct 718 ms 47964 KB Output is correct
37 Correct 707 ms 47968 KB Output is correct
38 Correct 260 ms 48056 KB Output is correct
39 Correct 246 ms 47964 KB Output is correct
40 Correct 245 ms 47964 KB Output is correct
41 Correct 691 ms 48072 KB Output is correct
42 Correct 678 ms 48216 KB Output is correct
43 Correct 692 ms 48040 KB Output is correct
44 Correct 247 ms 47964 KB Output is correct
45 Correct 260 ms 48004 KB Output is correct
46 Correct 257 ms 47964 KB Output is correct
47 Correct 692 ms 48016 KB Output is correct
48 Correct 692 ms 47960 KB Output is correct
49 Correct 695 ms 48000 KB Output is correct
50 Correct 255 ms 47996 KB Output is correct
51 Correct 263 ms 47976 KB Output is correct
52 Correct 273 ms 47996 KB Output is correct
53 Correct 265 ms 47988 KB Output is correct
54 Correct 258 ms 47972 KB Output is correct
55 Correct 256 ms 47988 KB Output is correct
56 Correct 12 ms 47708 KB Output is correct
57 Correct 7 ms 47708 KB Output is correct
58 Correct 8 ms 47964 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47708 KB Output is correct
2 Correct 6 ms 47708 KB Output is correct
3 Correct 11 ms 47708 KB Output is correct
4 Execution timed out 5096 ms 56464 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47708 KB Output is correct
2 Correct 36 ms 49756 KB Output is correct
3 Correct 47 ms 50012 KB Output is correct
4 Correct 48 ms 52228 KB Output is correct
5 Correct 85 ms 56444 KB Output is correct
6 Correct 91 ms 54976 KB Output is correct
7 Correct 86 ms 54132 KB Output is correct
8 Correct 80 ms 53840 KB Output is correct
9 Correct 77 ms 53672 KB Output is correct
10 Correct 72 ms 53588 KB Output is correct
11 Correct 72 ms 53632 KB Output is correct
12 Correct 71 ms 53840 KB Output is correct
13 Correct 65 ms 53844 KB Output is correct
14 Correct 62 ms 54084 KB Output is correct
15 Correct 98 ms 55704 KB Output is correct
16 Correct 81 ms 55376 KB Output is correct
17 Correct 77 ms 55380 KB Output is correct
18 Correct 77 ms 55436 KB Output is correct
19 Correct 78 ms 56532 KB Output is correct
20 Correct 79 ms 55376 KB Output is correct
21 Correct 79 ms 54528 KB Output is correct
22 Correct 97 ms 54024 KB Output is correct
23 Correct 73 ms 53932 KB Output is correct
24 Correct 73 ms 53776 KB Output is correct
25 Correct 70 ms 53588 KB Output is correct
26 Correct 68 ms 53736 KB Output is correct
27 Correct 78 ms 53576 KB Output is correct
28 Correct 65 ms 53560 KB Output is correct
29 Correct 62 ms 53592 KB Output is correct
30 Correct 63 ms 53364 KB Output is correct
31 Correct 61 ms 53840 KB Output is correct
32 Correct 56 ms 54024 KB Output is correct
33 Correct 64 ms 54604 KB Output is correct
34 Correct 101 ms 55632 KB Output is correct

Subtask #5
0 / 24.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 Correct 11 ms 47876 KB Output is correct
4 Execution timed out 5059 ms 53588 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.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 Correct 6 ms 47708 KB Output is correct
4 Correct 9 ms 47824 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47792 KB Output is correct
8 Correct 8 ms 47708 KB Output is correct
9 Correct 10 ms 47708 KB Output is correct
10 Correct 10 ms 47708 KB Output is correct
11 Correct 10 ms 47796 KB Output is correct
12 Correct 17 ms 47704 KB Output is correct
13 Correct 16 ms 47708 KB Output is correct
14 Correct 19 ms 47704 KB Output is correct
15 Correct 11 ms 47708 KB Output is correct
16 Correct 10 ms 47708 KB Output is correct
17 Correct 10 ms 47708 KB Output is correct
18 Correct 10 ms 47708 KB Output is correct
19 Correct 10 ms 47708 KB Output is correct
20 Correct 10 ms 47708 KB Output is correct
21 Correct 10 ms 47708 KB Output is correct
22 Correct 10 ms 47864 KB Output is correct
23 Correct 10 ms 47704 KB Output is correct
24 Correct 10 ms 47708 KB Output is correct
25 Correct 11 ms 47796 KB Output is correct
26 Correct 11 ms 47704 KB Output is correct
27 Correct 7 ms 47844 KB Output is correct
28 Correct 6 ms 47708 KB Output is correct
29 Correct 6 ms 47704 KB Output is correct
30 Correct 128 ms 47708 KB Output is correct
31 Correct 181 ms 48192 KB Output is correct
32 Correct 261 ms 47964 KB Output is correct
33 Correct 271 ms 47988 KB Output is correct
34 Correct 260 ms 47984 KB Output is correct
35 Correct 709 ms 47972 KB Output is correct
36 Correct 718 ms 47964 KB Output is correct
37 Correct 707 ms 47968 KB Output is correct
38 Correct 260 ms 48056 KB Output is correct
39 Correct 246 ms 47964 KB Output is correct
40 Correct 245 ms 47964 KB Output is correct
41 Correct 691 ms 48072 KB Output is correct
42 Correct 678 ms 48216 KB Output is correct
43 Correct 692 ms 48040 KB Output is correct
44 Correct 247 ms 47964 KB Output is correct
45 Correct 260 ms 48004 KB Output is correct
46 Correct 257 ms 47964 KB Output is correct
47 Correct 692 ms 48016 KB Output is correct
48 Correct 692 ms 47960 KB Output is correct
49 Correct 695 ms 48000 KB Output is correct
50 Correct 255 ms 47996 KB Output is correct
51 Correct 263 ms 47976 KB Output is correct
52 Correct 273 ms 47996 KB Output is correct
53 Correct 265 ms 47988 KB Output is correct
54 Correct 258 ms 47972 KB Output is correct
55 Correct 256 ms 47988 KB Output is correct
56 Correct 12 ms 47708 KB Output is correct
57 Correct 7 ms 47708 KB Output is correct
58 Correct 8 ms 47964 KB Output is correct
59 Correct 6 ms 47708 KB Output is correct
60 Correct 6 ms 47708 KB Output is correct
61 Correct 11 ms 47708 KB Output is correct
62 Execution timed out 5096 ms 56464 KB Time limit exceeded
63 Halted 0 ms 0 KB -