oj.uz

Submission #748942

# Submission time Handle Problem Language Result Execution time Memory
748942 2023-05-27T07:39:05 Z ETheBest3 Birthday gift (IZhO18_treearray) C++14
100 / 100
 2084 ms 113864 KB 
#include<bits/stdc++.h>
#define lli long long
#define endl "\n"
using namespace std;
const lli MAXN=200005, LOGN=25;
lli N, M, Q, a[MAXN], up[LOGN][MAXN], vh1, vh2, vh3, dep[MAXN], used[MAXN], type;
vector<lli> v[MAXN];
set<lli> pos1[MAXN], pos2[MAXN];
void dfs(lli vr){
    used[vr]=1;
    for(lli i=0; i<v[vr].size(); i++){
        if(used[v[vr][i]])continue;
        up[0][v[vr][i]]=vr;
        dep[v[vr][i]]=dep[vr]+1;
        dfs(v[vr][i]);
    }
    return;
}
lli lca(lli x, lli y){
    if(dep[x]<dep[y])swap(x, y);
    for(lli i=LOGN-1; i>=0; i--){
        if(dep[x]-(1<<i)>=dep[y]){
            x=up[i][x];
        }
    }
    if(x==y)return x;
    for(lli i=LOGN-1; i>=0; i--){
        if(up[i][x]!=up[i][y]){
            x=up[i][x];
            y=up[i][y];
        }
    }
    return up[0][x];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for(lli i=0; i<N-1; i++){
        cin>>vh1>>vh2;
        v[vh1].push_back(vh2);
        v[vh2].push_back(vh1);
    }
    dep[1]=1;
    dfs(1);
    for(lli st=1; st<LOGN; st++){
        for(lli i=1; i<=N; i++){
            up[st][i]=up[st-1][up[st-1][i]];
        }
    }
    for(lli i=1; i<=M; i++)cin>>a[i];
    for(lli i=1; i<=M; i++){
        pos1[a[i]].insert(i);
        if(i!=M)pos2[lca(a[i], a[i+1])].insert(i);
    }
    for(lli q=0; q<Q; q++){
        cin>>type;
        if(type==1){
            cin>>vh1>>vh2;
            pos1[a[vh1]].erase(vh1);
            if(vh1!=1)pos2[lca(a[vh1-1], a[vh1])].erase(vh1-1);
            if(vh1!=M)pos2[lca(a[vh1], a[vh1+1])].erase(vh1);
            a[vh1]=vh2;
            pos1[a[vh1]].insert(vh1);
            if(vh1!=1)pos2[lca(a[vh1-1], a[vh1])].insert(vh1-1);
            if(vh1!=M)pos2[lca(a[vh1], a[vh1+1])].insert(vh1);
        }else{
            cin>>vh1>>vh2>>vh3;
            auto it1=pos1[vh3].lower_bound(vh1), it2=pos2[vh3].lower_bound(vh1);
            if(it1!=pos1[vh3].end() and (*it1)<=vh2){
                cout<<(*it1)<<" "<<(*it1)<<endl;
                continue;
            }
            if(it2!=pos2[vh3].end() and (*it2)+1<=vh2){
                cout<<(*it2)<<" "<<(*it2)+1<<endl;
                continue;
            }
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'void dfs(long long int)':
treearray.cpp:11:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(lli i=0; i<v[vr].size(); i++){
      |                  ~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23968 KB n=5
2 Correct 12 ms 23952 KB n=100
3 Correct 13 ms 23920 KB n=100
4 Correct 13 ms 24000 KB n=100
5 Correct 13 ms 24020 KB n=100
6 Correct 13 ms 24020 KB n=100
7 Correct 12 ms 24020 KB n=100
8 Correct 14 ms 23964 KB n=100
9 Correct 13 ms 23948 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 13 ms 24020 KB n=100
12 Correct 12 ms 23944 KB n=100
13 Correct 15 ms 23940 KB n=100
14 Correct 14 ms 24020 KB n=100
15 Correct 13 ms 24040 KB n=100
16 Correct 13 ms 24020 KB n=100
17 Correct 13 ms 23988 KB n=100
18 Correct 12 ms 24020 KB n=100
19 Correct 12 ms 23984 KB n=100
20 Correct 13 ms 23948 KB n=100
21 Correct 12 ms 24148 KB n=100
22 Correct 12 ms 23932 KB n=100
23 Correct 12 ms 24044 KB n=100
24 Correct 12 ms 24048 KB n=100
25 Correct 13 ms 24020 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 13 ms 23952 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23968 KB n=5
2 Correct 12 ms 23952 KB n=100
3 Correct 13 ms 23920 KB n=100
4 Correct 13 ms 24000 KB n=100
5 Correct 13 ms 24020 KB n=100
6 Correct 13 ms 24020 KB n=100
7 Correct 12 ms 24020 KB n=100
8 Correct 14 ms 23964 KB n=100
9 Correct 13 ms 23948 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 13 ms 24020 KB n=100
12 Correct 12 ms 23944 KB n=100
13 Correct 15 ms 23940 KB n=100
14 Correct 14 ms 24020 KB n=100
15 Correct 13 ms 24040 KB n=100
16 Correct 13 ms 24020 KB n=100
17 Correct 13 ms 23988 KB n=100
18 Correct 12 ms 24020 KB n=100
19 Correct 12 ms 23984 KB n=100
20 Correct 13 ms 23948 KB n=100
21 Correct 12 ms 24148 KB n=100
22 Correct 12 ms 23932 KB n=100
23 Correct 12 ms 24044 KB n=100
24 Correct 12 ms 24048 KB n=100
25 Correct 13 ms 24020 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 13 ms 23952 KB n=100
28 Correct 15 ms 24080 KB n=500
29 Correct 15 ms 24220 KB n=500
30 Correct 14 ms 24148 KB n=500
31 Correct 13 ms 24148 KB n=500
32 Correct 16 ms 24088 KB n=500
33 Correct 13 ms 24092 KB n=500
34 Correct 13 ms 24080 KB n=500
35 Correct 14 ms 24148 KB n=500
36 Correct 12 ms 24148 KB n=500
37 Correct 13 ms 24076 KB n=500
38 Correct 13 ms 24164 KB n=500
39 Correct 15 ms 24148 KB n=500
40 Correct 15 ms 24192 KB n=500
41 Correct 12 ms 24188 KB n=500
42 Correct 13 ms 24080 KB n=500
43 Correct 16 ms 24080 KB n=500
44 Correct 16 ms 24080 KB n=500
45 Correct 13 ms 24148 KB n=500
46 Correct 13 ms 24148 KB n=500
47 Correct 13 ms 24124 KB n=500
48 Correct 13 ms 24148 KB n=500
49 Correct 13 ms 24116 KB n=500
50 Correct 13 ms 24080 KB n=500
51 Correct 13 ms 24148 KB n=500
52 Correct 13 ms 24148 KB n=500
53 Correct 15 ms 24148 KB n=500
54 Correct 14 ms 24224 KB n=500
55 Correct 13 ms 24020 KB n=278
56 Correct 13 ms 24140 KB n=500
57 Correct 14 ms 24212 KB n=500
58 Correct 14 ms 24148 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23968 KB n=5
2 Correct 12 ms 23952 KB n=100
3 Correct 13 ms 23920 KB n=100
4 Correct 13 ms 24000 KB n=100
5 Correct 13 ms 24020 KB n=100
6 Correct 13 ms 24020 KB n=100
7 Correct 12 ms 24020 KB n=100
8 Correct 14 ms 23964 KB n=100
9 Correct 13 ms 23948 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 13 ms 24020 KB n=100
12 Correct 12 ms 23944 KB n=100
13 Correct 15 ms 23940 KB n=100
14 Correct 14 ms 24020 KB n=100
15 Correct 13 ms 24040 KB n=100
16 Correct 13 ms 24020 KB n=100
17 Correct 13 ms 23988 KB n=100
18 Correct 12 ms 24020 KB n=100
19 Correct 12 ms 23984 KB n=100
20 Correct 13 ms 23948 KB n=100
21 Correct 12 ms 24148 KB n=100
22 Correct 12 ms 23932 KB n=100
23 Correct 12 ms 24044 KB n=100
24 Correct 12 ms 24048 KB n=100
25 Correct 13 ms 24020 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 13 ms 23952 KB n=100
28 Correct 15 ms 24080 KB n=500
29 Correct 15 ms 24220 KB n=500
30 Correct 14 ms 24148 KB n=500
31 Correct 13 ms 24148 KB n=500
32 Correct 16 ms 24088 KB n=500
33 Correct 13 ms 24092 KB n=500
34 Correct 13 ms 24080 KB n=500
35 Correct 14 ms 24148 KB n=500
36 Correct 12 ms 24148 KB n=500
37 Correct 13 ms 24076 KB n=500
38 Correct 13 ms 24164 KB n=500
39 Correct 15 ms 24148 KB n=500
40 Correct 15 ms 24192 KB n=500
41 Correct 12 ms 24188 KB n=500
42 Correct 13 ms 24080 KB n=500
43 Correct 16 ms 24080 KB n=500
44 Correct 16 ms 24080 KB n=500
45 Correct 13 ms 24148 KB n=500
46 Correct 13 ms 24148 KB n=500
47 Correct 13 ms 24124 KB n=500
48 Correct 13 ms 24148 KB n=500
49 Correct 13 ms 24116 KB n=500
50 Correct 13 ms 24080 KB n=500
51 Correct 13 ms 24148 KB n=500
52 Correct 13 ms 24148 KB n=500
53 Correct 15 ms 24148 KB n=500
54 Correct 14 ms 24224 KB n=500
55 Correct 13 ms 24020 KB n=278
56 Correct 13 ms 24140 KB n=500
57 Correct 14 ms 24212 KB n=500
58 Correct 14 ms 24148 KB n=500
59 Correct 18 ms 24720 KB n=2000
60 Correct 16 ms 24788 KB n=2000
61 Correct 16 ms 24732 KB n=2000
62 Correct 20 ms 24792 KB n=2000
63 Correct 17 ms 24660 KB n=2000
64 Correct 17 ms 24712 KB n=2000
65 Correct 17 ms 24728 KB n=2000
66 Correct 17 ms 24828 KB n=2000
67 Correct 18 ms 24660 KB n=2000
68 Correct 17 ms 24720 KB n=2000
69 Correct 16 ms 24788 KB n=2000
70 Correct 17 ms 24660 KB n=2000
71 Correct 17 ms 24776 KB n=2000
72 Correct 16 ms 24744 KB n=2000
73 Correct 16 ms 24700 KB n=2000
74 Correct 17 ms 24724 KB n=1844
75 Correct 21 ms 24720 KB n=2000
76 Correct 19 ms 24656 KB n=2000
77 Correct 17 ms 24660 KB n=2000
78 Correct 17 ms 24752 KB n=2000
79 Correct 16 ms 24748 KB n=2000
80 Correct 17 ms 24788 KB n=2000
81 Correct 16 ms 24812 KB n=2000
82 Correct 16 ms 24660 KB n=2000
83 Correct 17 ms 24788 KB n=2000
84 Correct 18 ms 24720 KB n=2000
85 Correct 18 ms 24788 KB n=2000
86 Correct 18 ms 24728 KB n=2000
87 Correct 18 ms 24764 KB n=2000
88 Correct 16 ms 24876 KB n=2000
89 Correct 16 ms 24780 KB n=2000
90 Correct 15 ms 24788 KB n=2000
91 Correct 15 ms 24660 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23968 KB n=5
2 Correct 12 ms 23952 KB n=100
3 Correct 13 ms 23920 KB n=100
4 Correct 13 ms 24000 KB n=100
5 Correct 13 ms 24020 KB n=100
6 Correct 13 ms 24020 KB n=100
7 Correct 12 ms 24020 KB n=100
8 Correct 14 ms 23964 KB n=100
9 Correct 13 ms 23948 KB n=100
10 Correct 13 ms 23936 KB n=100
11 Correct 13 ms 24020 KB n=100
12 Correct 12 ms 23944 KB n=100
13 Correct 15 ms 23940 KB n=100
14 Correct 14 ms 24020 KB n=100
15 Correct 13 ms 24040 KB n=100
16 Correct 13 ms 24020 KB n=100
17 Correct 13 ms 23988 KB n=100
18 Correct 12 ms 24020 KB n=100
19 Correct 12 ms 23984 KB n=100
20 Correct 13 ms 23948 KB n=100
21 Correct 12 ms 24148 KB n=100
22 Correct 12 ms 23932 KB n=100
23 Correct 12 ms 24044 KB n=100
24 Correct 12 ms 24048 KB n=100
25 Correct 13 ms 24020 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 13 ms 23952 KB n=100
28 Correct 15 ms 24080 KB n=500
29 Correct 15 ms 24220 KB n=500
30 Correct 14 ms 24148 KB n=500
31 Correct 13 ms 24148 KB n=500
32 Correct 16 ms 24088 KB n=500
33 Correct 13 ms 24092 KB n=500
34 Correct 13 ms 24080 KB n=500
35 Correct 14 ms 24148 KB n=500
36 Correct 12 ms 24148 KB n=500
37 Correct 13 ms 24076 KB n=500
38 Correct 13 ms 24164 KB n=500
39 Correct 15 ms 24148 KB n=500
40 Correct 15 ms 24192 KB n=500
41 Correct 12 ms 24188 KB n=500
42 Correct 13 ms 24080 KB n=500
43 Correct 16 ms 24080 KB n=500
44 Correct 16 ms 24080 KB n=500
45 Correct 13 ms 24148 KB n=500
46 Correct 13 ms 24148 KB n=500
47 Correct 13 ms 24124 KB n=500
48 Correct 13 ms 24148 KB n=500
49 Correct 13 ms 24116 KB n=500
50 Correct 13 ms 24080 KB n=500
51 Correct 13 ms 24148 KB n=500
52 Correct 13 ms 24148 KB n=500
53 Correct 15 ms 24148 KB n=500
54 Correct 14 ms 24224 KB n=500
55 Correct 13 ms 24020 KB n=278
56 Correct 13 ms 24140 KB n=500
57 Correct 14 ms 24212 KB n=500
58 Correct 14 ms 24148 KB n=500
59 Correct 18 ms 24720 KB n=2000
60 Correct 16 ms 24788 KB n=2000
61 Correct 16 ms 24732 KB n=2000
62 Correct 20 ms 24792 KB n=2000
63 Correct 17 ms 24660 KB n=2000
64 Correct 17 ms 24712 KB n=2000
65 Correct 17 ms 24728 KB n=2000
66 Correct 17 ms 24828 KB n=2000
67 Correct 18 ms 24660 KB n=2000
68 Correct 17 ms 24720 KB n=2000
69 Correct 16 ms 24788 KB n=2000
70 Correct 17 ms 24660 KB n=2000
71 Correct 17 ms 24776 KB n=2000
72 Correct 16 ms 24744 KB n=2000
73 Correct 16 ms 24700 KB n=2000
74 Correct 17 ms 24724 KB n=1844
75 Correct 21 ms 24720 KB n=2000
76 Correct 19 ms 24656 KB n=2000
77 Correct 17 ms 24660 KB n=2000
78 Correct 17 ms 24752 KB n=2000
79 Correct 16 ms 24748 KB n=2000
80 Correct 17 ms 24788 KB n=2000
81 Correct 16 ms 24812 KB n=2000
82 Correct 16 ms 24660 KB n=2000
83 Correct 17 ms 24788 KB n=2000
84 Correct 18 ms 24720 KB n=2000
85 Correct 18 ms 24788 KB n=2000
86 Correct 18 ms 24728 KB n=2000
87 Correct 18 ms 24764 KB n=2000
88 Correct 16 ms 24876 KB n=2000
89 Correct 16 ms 24780 KB n=2000
90 Correct 15 ms 24788 KB n=2000
91 Correct 15 ms 24660 KB n=2000
92 Correct 1939 ms 101936 KB n=200000
93 Correct 1495 ms 108588 KB n=200000
94 Correct 1211 ms 112504 KB n=200000
95 Correct 1907 ms 101792 KB n=200000
96 Correct 1859 ms 101880 KB n=200000
97 Correct 1713 ms 107516 KB n=200000
98 Correct 1859 ms 101968 KB n=200000
99 Correct 2084 ms 102492 KB n=200000
100 Correct 1860 ms 101924 KB n=200000
101 Correct 1132 ms 113864 KB n=200000
102 Correct 808 ms 103196 KB n=200000
103 Correct 818 ms 103224 KB n=200000
104 Correct 809 ms 103132 KB n=200000
105 Correct 842 ms 103692 KB n=200000
106 Correct 786 ms 103620 KB n=200000
107 Correct 800 ms 103588 KB n=200000
108 Correct 1972 ms 102012 KB n=200000
109 Correct 1933 ms 102164 KB n=200000
110 Correct 1994 ms 102060 KB n=200000
111 Correct 1640 ms 101272 KB n=200000
112 Correct 1169 ms 112868 KB n=200000
113 Correct 1651 ms 107204 KB n=200000
114 Correct 1601 ms 101364 KB n=200000
115 Correct 1986 ms 104528 KB n=200000
116 Correct 1753 ms 101836 KB n=200000
117 Correct 1091 ms 113120 KB n=200000
118 Correct 1826 ms 105712 KB n=200000
119 Correct 1927 ms 101928 KB n=200000
120 Correct 1079 ms 112788 KB n=200000
121 Correct 1030 ms 112680 KB n=200000
122 Correct 1043 ms 113052 KB n=200000
123 Correct 818 ms 103508 KB n=200000
124 Correct 243 ms 43108 KB n=25264