oj.uz

Submission #873753

# Submission time Handle Problem Language Result Execution time Memory
873753 2023-11-15T15:50:01 Z maxFedorchuk Birthday gift (IZhO18_treearray) C++14
100 / 100
 1569 ms 106068 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10;
const long long lg=22;

vector < long long > mas[MX];
set < long long > mlca[MX];
set < long long > mel[MX];
long long prd[lg][MX]={0};

long long bbb[MX];
long long el[MX];
long long tin[MX];
long long tou[MX];
long long timer=0;

void DFS(long long zar,long long mun)
{
    timer++;
    tin[zar]=timer;

    prd[0][zar]=mun;
    for(long long i=1;i<lg;i++)
    {
        prd[i][zar]=prd[i-1][prd[i-1][zar]];
    }

    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
        }
    }

    timer++;
    tou[zar]=timer;

    return;
}


long long fun_lca(long long a,long long b)
{
    if(tin[a]<=tin[b] && tou[b]<=tou[a])
    {
        return a;
    }

    if(tin[b]<=tin[a] && tou[a]<=tou[b])
    {
        return b;
    }

    for(long long i=lg-1;i>=0;i--)
    {
        if(tin[prd[i][a]]<=tin[b] && tou[b]<=tou[prd[i][a]])
        {

        }
        else
        {
            a=prd[i][a];
        }
    }

    return prd[0][a];
}

long long n,m,q;

void upd(long long pos,long long zn)
{
    mel[el[pos]].erase(pos);
    el[pos]=zn;
    mel[el[pos]].insert(pos);

    if(pos!=1)
    {
        mlca[bbb[pos-1]].erase(pos-1);
        bbb[pos-1]=fun_lca(el[pos-1],el[pos]);
        mlca[bbb[pos-1]].insert(pos-1);
    }

    if(pos!=m)
    {
        mlca[bbb[pos]].erase(pos);
        bbb[pos]=fun_lca(el[pos],el[pos+1]);
        mlca[bbb[pos]].insert(pos);
    }

    return;
}

void get_zn(long long l,long long r,long long zn)
{
    auto it1=mel[zn].lower_bound(l);
    auto it2=mlca[zn].lower_bound(l);

    if(it1!=mel[zn].end() && (*it1)<=r)
    {
        cout<<(*it1)<<" "<<(*it1)<<"\n";
    }
    else
    {
        if(it2!=mlca[zn].end() && (*it2)<r)
        {
            cout<<(*it2)<<" "<<(*it2)+1<<"\n";
        }
        else
        {
            cout<<"-1 -1\n";
        }
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m>>q;

    long long a,b,c;
    for(long long i=1;i<n;i++)
    {
        cin>>a>>b;
        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    tin[0]=0;
    DFS(1,0);
    timer++;
    tou[0]=timer;

    for(long long i=1;i<=m;i++)
    {
        cin>>el[i];
    }

    for(long long i=1;i<=m;i++)
    {
        upd(i,el[i]);
    }

    while(q--)
    {
        long long zp;
        cin>>zp;

        if(zp==1)
        {
            cin>>a>>b;
            upd(a,b);
        }
        else
        {
            cin>>a>>b>>c;
            get_zn(a,b,c);
        }
    }

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64348 KB n=5
2 Correct 9 ms 64348 KB n=100
3 Correct 9 ms 64348 KB n=100
4 Correct 9 ms 64340 KB n=100
5 Correct 10 ms 64356 KB n=100
6 Correct 10 ms 64348 KB n=100
7 Correct 9 ms 64348 KB n=100
8 Correct 9 ms 64344 KB n=100
9 Correct 9 ms 64348 KB n=100
10 Correct 9 ms 64344 KB n=100
11 Correct 9 ms 64344 KB n=100
12 Correct 9 ms 64348 KB n=100
13 Correct 9 ms 64348 KB n=100
14 Correct 10 ms 64348 KB n=100
15 Correct 9 ms 64344 KB n=100
16 Correct 9 ms 64348 KB n=100
17 Correct 9 ms 64348 KB n=100
18 Correct 10 ms 64604 KB n=100
19 Correct 9 ms 64348 KB n=100
20 Correct 9 ms 64348 KB n=100
21 Correct 10 ms 64488 KB n=100
22 Correct 9 ms 64348 KB n=100
23 Correct 9 ms 64348 KB n=100
24 Correct 9 ms 64488 KB n=100
25 Correct 9 ms 64348 KB n=100
26 Correct 10 ms 64344 KB n=12
27 Correct 10 ms 64348 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64348 KB n=5
2 Correct 9 ms 64348 KB n=100
3 Correct 9 ms 64348 KB n=100
4 Correct 9 ms 64340 KB n=100
5 Correct 10 ms 64356 KB n=100
6 Correct 10 ms 64348 KB n=100
7 Correct 9 ms 64348 KB n=100
8 Correct 9 ms 64344 KB n=100
9 Correct 9 ms 64348 KB n=100
10 Correct 9 ms 64344 KB n=100
11 Correct 9 ms 64344 KB n=100
12 Correct 9 ms 64348 KB n=100
13 Correct 9 ms 64348 KB n=100
14 Correct 10 ms 64348 KB n=100
15 Correct 9 ms 64344 KB n=100
16 Correct 9 ms 64348 KB n=100
17 Correct 9 ms 64348 KB n=100
18 Correct 10 ms 64604 KB n=100
19 Correct 9 ms 64348 KB n=100
20 Correct 9 ms 64348 KB n=100
21 Correct 10 ms 64488 KB n=100
22 Correct 9 ms 64348 KB n=100
23 Correct 9 ms 64348 KB n=100
24 Correct 9 ms 64488 KB n=100
25 Correct 9 ms 64348 KB n=100
26 Correct 10 ms 64344 KB n=12
27 Correct 10 ms 64348 KB n=100
28 Correct 10 ms 64344 KB n=500
29 Correct 10 ms 64348 KB n=500
30 Correct 10 ms 64348 KB n=500
31 Correct 10 ms 64576 KB n=500
32 Correct 11 ms 64348 KB n=500
33 Correct 10 ms 64600 KB n=500
34 Correct 10 ms 64348 KB n=500
35 Correct 10 ms 64348 KB n=500
36 Correct 11 ms 64556 KB n=500
37 Correct 10 ms 64456 KB n=500
38 Correct 10 ms 64416 KB n=500
39 Correct 10 ms 64344 KB n=500
40 Correct 10 ms 64348 KB n=500
41 Correct 10 ms 64348 KB n=500
42 Correct 11 ms 64412 KB n=500
43 Correct 10 ms 64344 KB n=500
44 Correct 10 ms 64348 KB n=500
45 Correct 10 ms 64344 KB n=500
46 Correct 10 ms 64348 KB n=500
47 Correct 10 ms 64348 KB n=500
48 Correct 10 ms 64348 KB n=500
49 Correct 11 ms 64348 KB n=500
50 Correct 10 ms 64344 KB n=500
51 Correct 11 ms 64600 KB n=500
52 Correct 10 ms 64348 KB n=500
53 Correct 10 ms 64348 KB n=500
54 Correct 10 ms 64348 KB n=500
55 Correct 11 ms 64348 KB n=278
56 Correct 10 ms 64580 KB n=500
57 Correct 10 ms 64584 KB n=500
58 Correct 10 ms 64444 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64348 KB n=5
2 Correct 9 ms 64348 KB n=100
3 Correct 9 ms 64348 KB n=100
4 Correct 9 ms 64340 KB n=100
5 Correct 10 ms 64356 KB n=100
6 Correct 10 ms 64348 KB n=100
7 Correct 9 ms 64348 KB n=100
8 Correct 9 ms 64344 KB n=100
9 Correct 9 ms 64348 KB n=100
10 Correct 9 ms 64344 KB n=100
11 Correct 9 ms 64344 KB n=100
12 Correct 9 ms 64348 KB n=100
13 Correct 9 ms 64348 KB n=100
14 Correct 10 ms 64348 KB n=100
15 Correct 9 ms 64344 KB n=100
16 Correct 9 ms 64348 KB n=100
17 Correct 9 ms 64348 KB n=100
18 Correct 10 ms 64604 KB n=100
19 Correct 9 ms 64348 KB n=100
20 Correct 9 ms 64348 KB n=100
21 Correct 10 ms 64488 KB n=100
22 Correct 9 ms 64348 KB n=100
23 Correct 9 ms 64348 KB n=100
24 Correct 9 ms 64488 KB n=100
25 Correct 9 ms 64348 KB n=100
26 Correct 10 ms 64344 KB n=12
27 Correct 10 ms 64348 KB n=100
28 Correct 10 ms 64344 KB n=500
29 Correct 10 ms 64348 KB n=500
30 Correct 10 ms 64348 KB n=500
31 Correct 10 ms 64576 KB n=500
32 Correct 11 ms 64348 KB n=500
33 Correct 10 ms 64600 KB n=500
34 Correct 10 ms 64348 KB n=500
35 Correct 10 ms 64348 KB n=500
36 Correct 11 ms 64556 KB n=500
37 Correct 10 ms 64456 KB n=500
38 Correct 10 ms 64416 KB n=500
39 Correct 10 ms 64344 KB n=500
40 Correct 10 ms 64348 KB n=500
41 Correct 10 ms 64348 KB n=500
42 Correct 11 ms 64412 KB n=500
43 Correct 10 ms 64344 KB n=500
44 Correct 10 ms 64348 KB n=500
45 Correct 10 ms 64344 KB n=500
46 Correct 10 ms 64348 KB n=500
47 Correct 10 ms 64348 KB n=500
48 Correct 10 ms 64348 KB n=500
49 Correct 11 ms 64348 KB n=500
50 Correct 10 ms 64344 KB n=500
51 Correct 11 ms 64600 KB n=500
52 Correct 10 ms 64348 KB n=500
53 Correct 10 ms 64348 KB n=500
54 Correct 10 ms 64348 KB n=500
55 Correct 11 ms 64348 KB n=278
56 Correct 10 ms 64580 KB n=500
57 Correct 10 ms 64584 KB n=500
58 Correct 10 ms 64444 KB n=500
59 Correct 13 ms 64608 KB n=2000
60 Correct 12 ms 65112 KB n=2000
61 Correct 12 ms 64856 KB n=2000
62 Correct 13 ms 64604 KB n=2000
63 Correct 14 ms 64604 KB n=2000
64 Correct 12 ms 64856 KB n=2000
65 Correct 12 ms 64604 KB n=2000
66 Correct 11 ms 64872 KB n=2000
67 Correct 12 ms 64624 KB n=2000
68 Correct 12 ms 64860 KB n=2000
69 Correct 12 ms 64604 KB n=2000
70 Correct 12 ms 64600 KB n=2000
71 Correct 11 ms 64604 KB n=2000
72 Correct 12 ms 64604 KB n=2000
73 Correct 12 ms 64592 KB n=2000
74 Correct 12 ms 64856 KB n=1844
75 Correct 13 ms 64604 KB n=2000
76 Correct 12 ms 64604 KB n=2000
77 Correct 14 ms 64604 KB n=2000
78 Correct 12 ms 64604 KB n=2000
79 Correct 12 ms 64604 KB n=2000
80 Correct 11 ms 64856 KB n=2000
81 Correct 12 ms 64604 KB n=2000
82 Correct 13 ms 64612 KB n=2000
83 Correct 13 ms 64860 KB n=2000
84 Correct 12 ms 64600 KB n=2000
85 Correct 12 ms 65100 KB n=2000
86 Correct 12 ms 64600 KB n=2000
87 Correct 13 ms 64604 KB n=2000
88 Correct 12 ms 64860 KB n=2000
89 Correct 11 ms 65112 KB n=2000
90 Correct 11 ms 64860 KB n=2000
91 Correct 11 ms 64600 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64348 KB n=5
2 Correct 9 ms 64348 KB n=100
3 Correct 9 ms 64348 KB n=100
4 Correct 9 ms 64340 KB n=100
5 Correct 10 ms 64356 KB n=100
6 Correct 10 ms 64348 KB n=100
7 Correct 9 ms 64348 KB n=100
8 Correct 9 ms 64344 KB n=100
9 Correct 9 ms 64348 KB n=100
10 Correct 9 ms 64344 KB n=100
11 Correct 9 ms 64344 KB n=100
12 Correct 9 ms 64348 KB n=100
13 Correct 9 ms 64348 KB n=100
14 Correct 10 ms 64348 KB n=100
15 Correct 9 ms 64344 KB n=100
16 Correct 9 ms 64348 KB n=100
17 Correct 9 ms 64348 KB n=100
18 Correct 10 ms 64604 KB n=100
19 Correct 9 ms 64348 KB n=100
20 Correct 9 ms 64348 KB n=100
21 Correct 10 ms 64488 KB n=100
22 Correct 9 ms 64348 KB n=100
23 Correct 9 ms 64348 KB n=100
24 Correct 9 ms 64488 KB n=100
25 Correct 9 ms 64348 KB n=100
26 Correct 10 ms 64344 KB n=12
27 Correct 10 ms 64348 KB n=100
28 Correct 10 ms 64344 KB n=500
29 Correct 10 ms 64348 KB n=500
30 Correct 10 ms 64348 KB n=500
31 Correct 10 ms 64576 KB n=500
32 Correct 11 ms 64348 KB n=500
33 Correct 10 ms 64600 KB n=500
34 Correct 10 ms 64348 KB n=500
35 Correct 10 ms 64348 KB n=500
36 Correct 11 ms 64556 KB n=500
37 Correct 10 ms 64456 KB n=500
38 Correct 10 ms 64416 KB n=500
39 Correct 10 ms 64344 KB n=500
40 Correct 10 ms 64348 KB n=500
41 Correct 10 ms 64348 KB n=500
42 Correct 11 ms 64412 KB n=500
43 Correct 10 ms 64344 KB n=500
44 Correct 10 ms 64348 KB n=500
45 Correct 10 ms 64344 KB n=500
46 Correct 10 ms 64348 KB n=500
47 Correct 10 ms 64348 KB n=500
48 Correct 10 ms 64348 KB n=500
49 Correct 11 ms 64348 KB n=500
50 Correct 10 ms 64344 KB n=500
51 Correct 11 ms 64600 KB n=500
52 Correct 10 ms 64348 KB n=500
53 Correct 10 ms 64348 KB n=500
54 Correct 10 ms 64348 KB n=500
55 Correct 11 ms 64348 KB n=278
56 Correct 10 ms 64580 KB n=500
57 Correct 10 ms 64584 KB n=500
58 Correct 10 ms 64444 KB n=500
59 Correct 13 ms 64608 KB n=2000
60 Correct 12 ms 65112 KB n=2000
61 Correct 12 ms 64856 KB n=2000
62 Correct 13 ms 64604 KB n=2000
63 Correct 14 ms 64604 KB n=2000
64 Correct 12 ms 64856 KB n=2000
65 Correct 12 ms 64604 KB n=2000
66 Correct 11 ms 64872 KB n=2000
67 Correct 12 ms 64624 KB n=2000
68 Correct 12 ms 64860 KB n=2000
69 Correct 12 ms 64604 KB n=2000
70 Correct 12 ms 64600 KB n=2000
71 Correct 11 ms 64604 KB n=2000
72 Correct 12 ms 64604 KB n=2000
73 Correct 12 ms 64592 KB n=2000
74 Correct 12 ms 64856 KB n=1844
75 Correct 13 ms 64604 KB n=2000
76 Correct 12 ms 64604 KB n=2000
77 Correct 14 ms 64604 KB n=2000
78 Correct 12 ms 64604 KB n=2000
79 Correct 12 ms 64604 KB n=2000
80 Correct 11 ms 64856 KB n=2000
81 Correct 12 ms 64604 KB n=2000
82 Correct 13 ms 64612 KB n=2000
83 Correct 13 ms 64860 KB n=2000
84 Correct 12 ms 64600 KB n=2000
85 Correct 12 ms 65100 KB n=2000
86 Correct 12 ms 64600 KB n=2000
87 Correct 13 ms 64604 KB n=2000
88 Correct 12 ms 64860 KB n=2000
89 Correct 11 ms 65112 KB n=2000
90 Correct 11 ms 64860 KB n=2000
91 Correct 11 ms 64600 KB n=2000
92 Correct 1528 ms 98056 KB n=200000
93 Correct 898 ms 102368 KB n=200000
94 Correct 525 ms 105024 KB n=200000
95 Correct 1569 ms 98056 KB n=200000
96 Correct 1425 ms 97688 KB n=200000
97 Correct 989 ms 101504 KB n=200000
98 Correct 1427 ms 97728 KB n=200000
99 Correct 1475 ms 98028 KB n=200000
100 Correct 1443 ms 97740 KB n=200000
101 Correct 387 ms 106068 KB n=200000
102 Correct 746 ms 98640 KB n=200000
103 Correct 686 ms 98808 KB n=200000
104 Correct 694 ms 98696 KB n=200000
105 Correct 731 ms 99012 KB n=200000
106 Correct 684 ms 98892 KB n=200000
107 Correct 697 ms 99216 KB n=200000
108 Correct 1321 ms 97616 KB n=200000
109 Correct 1338 ms 97976 KB n=200000
110 Correct 1273 ms 97616 KB n=200000
111 Correct 1203 ms 97120 KB n=200000
112 Correct 473 ms 105704 KB n=200000
113 Correct 926 ms 101716 KB n=200000
114 Correct 1182 ms 97212 KB n=200000
115 Correct 1283 ms 99924 KB n=200000
116 Correct 1361 ms 97488 KB n=200000
117 Correct 418 ms 105616 KB n=200000
118 Correct 1163 ms 100436 KB n=200000
119 Correct 1389 ms 97880 KB n=200000
120 Correct 358 ms 105324 KB n=200000
121 Correct 354 ms 105276 KB n=200000
122 Correct 335 ms 105424 KB n=200000
123 Correct 768 ms 99020 KB n=200000
124 Correct 111 ms 77008 KB n=25264