# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
140748 | 2019-08-04T23:47:24 Z | rzbt | Birthday gift (IZhO18_treearray) | C++14 | 1652 ms | 84868 KB |
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 200005 using namespace std; int n,m,q; vector<int> niz[MAXN]; int predak[MAXN][21]; int dubina[MAXN]; int a[MAXN]; set<int> s[MAXN],sp[MAXN]; void dfs(int t,int o,int h){ predak[t][0]=o; dubina[t]=h; for(auto x:niz[t]) if(x!=o) dfs(x,t,h+1); } int lca(int a, int b){ if(dubina[b]>dubina[a])swap(a,b); for(int j=20;j>=0;j--){ if(dubina[predak[a][j]]>=dubina[b])a=predak[a][j]; } if(a==b)return a; for(int j=20;j>=0;j--){ if(predak[a][j]!=predak[b][j]){ a=predak[a][j]; b=predak[b][j]; } } return predak[a][0]; } int main() { scanf("%d %d %d", &n, &m, &q); for(int i=1;i<n;i++){ int t1,t2; scanf("%d %d", &t1, &t2); niz[t1].pb(t2); niz[t2].pb(t1); } dfs(1,0,1); for(int j=1;j<21;j++) for(int i=1;i<=n;i++) predak[i][j]=predak[predak[i][j-1]][j-1]; for(int i=1;i<=m;i++) scanf("%d",a+i); for(int i=1;i<m;i++) s[lca(a[i],a[i+1])].insert(i); for(int i=1;i<=m;i++) sp[a[i]].insert(i); while(q--){ int qt; //FITTER HAPPIER MORE PRODUCTIVE scanf("%d", &qt); if(qt==1){ int pos,x; scanf("%d %d", &pos,&x); sp[a[pos]].erase(pos); if(pos>1)s[lca(a[pos],a[pos-1])].erase(pos-1); if(pos<m)s[lca(a[pos],a[pos+1])].erase(pos); a[pos]=x; sp[a[pos]].insert(pos); if(pos>1)s[lca(a[pos],a[pos-1])].insert(pos-1); if(pos<m)s[lca(a[pos],a[pos+1])].insert(pos); }else if(qt==2){ int l,r,x; scanf("%d %d %d", &l, &r, &x); //printf(" %d %d\n",sp[x].size(),s[x].size()); auto t1=sp[x].lower_bound(l); auto t2=s[x].lower_bound(l); //printf(" %d %d %d %d\n",sp[x].size(),s[x].size(),t1,t2); if(t1!=sp[x].end() && (*t1)<=r)printf("%d %d\n",*t1,*t1); else if(t2!=s[x].end() && (*t2)<r)printf("%d %d\n",*t2,(*t2)+1); else printf("-1 -1\n"); } else{ int x,y; scanf("%d %d", &x, &y); printf(" %d\n",lca(a[x],a[y])); } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | n=5 |
2 | Correct | 23 ms | 23800 KB | n=100 |
3 | Correct | 22 ms | 23800 KB | n=100 |
4 | Correct | 23 ms | 23800 KB | n=100 |
5 | Correct | 23 ms | 23772 KB | n=100 |
6 | Correct | 22 ms | 23800 KB | n=100 |
7 | Correct | 23 ms | 23800 KB | n=100 |
8 | Correct | 23 ms | 23804 KB | n=100 |
9 | Correct | 22 ms | 23800 KB | n=100 |
10 | Correct | 23 ms | 23800 KB | n=100 |
11 | Correct | 22 ms | 23800 KB | n=100 |
12 | Correct | 23 ms | 23928 KB | n=100 |
13 | Correct | 22 ms | 23800 KB | n=100 |
14 | Correct | 23 ms | 23800 KB | n=100 |
15 | Correct | 23 ms | 23800 KB | n=100 |
16 | Correct | 23 ms | 23800 KB | n=100 |
17 | Correct | 23 ms | 23880 KB | n=100 |
18 | Correct | 23 ms | 23928 KB | n=100 |
19 | Correct | 23 ms | 23800 KB | n=100 |
20 | Correct | 23 ms | 23800 KB | n=100 |
21 | Correct | 22 ms | 23800 KB | n=100 |
22 | Correct | 23 ms | 23800 KB | n=100 |
23 | Correct | 23 ms | 23800 KB | n=100 |
24 | Correct | 23 ms | 23800 KB | n=100 |
25 | Correct | 22 ms | 23928 KB | n=100 |
26 | Correct | 23 ms | 23800 KB | n=12 |
27 | Correct | 23 ms | 23800 KB | n=100 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | n=5 |
2 | Correct | 23 ms | 23800 KB | n=100 |
3 | Correct | 22 ms | 23800 KB | n=100 |
4 | Correct | 23 ms | 23800 KB | n=100 |
5 | Correct | 23 ms | 23772 KB | n=100 |
6 | Correct | 22 ms | 23800 KB | n=100 |
7 | Correct | 23 ms | 23800 KB | n=100 |
8 | Correct | 23 ms | 23804 KB | n=100 |
9 | Correct | 22 ms | 23800 KB | n=100 |
10 | Correct | 23 ms | 23800 KB | n=100 |
11 | Correct | 22 ms | 23800 KB | n=100 |
12 | Correct | 23 ms | 23928 KB | n=100 |
13 | Correct | 22 ms | 23800 KB | n=100 |
14 | Correct | 23 ms | 23800 KB | n=100 |
15 | Correct | 23 ms | 23800 KB | n=100 |
16 | Correct | 23 ms | 23800 KB | n=100 |
17 | Correct | 23 ms | 23880 KB | n=100 |
18 | Correct | 23 ms | 23928 KB | n=100 |
19 | Correct | 23 ms | 23800 KB | n=100 |
20 | Correct | 23 ms | 23800 KB | n=100 |
21 | Correct | 22 ms | 23800 KB | n=100 |
22 | Correct | 23 ms | 23800 KB | n=100 |
23 | Correct | 23 ms | 23800 KB | n=100 |
24 | Correct | 23 ms | 23800 KB | n=100 |
25 | Correct | 22 ms | 23928 KB | n=100 |
26 | Correct | 23 ms | 23800 KB | n=12 |
27 | Correct | 23 ms | 23800 KB | n=100 |
28 | Correct | 23 ms | 23928 KB | n=500 |
29 | Correct | 23 ms | 23928 KB | n=500 |
30 | Correct | 23 ms | 23928 KB | n=500 |
31 | Correct | 24 ms | 23928 KB | n=500 |
32 | Correct | 23 ms | 23928 KB | n=500 |
33 | Correct | 24 ms | 23928 KB | n=500 |
34 | Correct | 23 ms | 23928 KB | n=500 |
35 | Correct | 23 ms | 23928 KB | n=500 |
36 | Correct | 23 ms | 23928 KB | n=500 |
37 | Correct | 23 ms | 23904 KB | n=500 |
38 | Correct | 23 ms | 23928 KB | n=500 |
39 | Correct | 23 ms | 23900 KB | n=500 |
40 | Correct | 27 ms | 23928 KB | n=500 |
41 | Correct | 23 ms | 23928 KB | n=500 |
42 | Correct | 23 ms | 23928 KB | n=500 |
43 | Correct | 29 ms | 23928 KB | n=500 |
44 | Correct | 29 ms | 23928 KB | n=500 |
45 | Correct | 26 ms | 24056 KB | n=500 |
46 | Correct | 24 ms | 23928 KB | n=500 |
47 | Correct | 24 ms | 23976 KB | n=500 |
48 | Correct | 24 ms | 23932 KB | n=500 |
49 | Correct | 30 ms | 23928 KB | n=500 |
50 | Correct | 23 ms | 23928 KB | n=500 |
51 | Correct | 24 ms | 23932 KB | n=500 |
52 | Correct | 24 ms | 23928 KB | n=500 |
53 | Correct | 24 ms | 23928 KB | n=500 |
54 | Correct | 23 ms | 23928 KB | n=500 |
55 | Correct | 23 ms | 23928 KB | n=278 |
56 | Correct | 23 ms | 23928 KB | n=500 |
57 | Correct | 24 ms | 23928 KB | n=500 |
58 | Correct | 23 ms | 23928 KB | n=500 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | n=5 |
2 | Correct | 23 ms | 23800 KB | n=100 |
3 | Correct | 22 ms | 23800 KB | n=100 |
4 | Correct | 23 ms | 23800 KB | n=100 |
5 | Correct | 23 ms | 23772 KB | n=100 |
6 | Correct | 22 ms | 23800 KB | n=100 |
7 | Correct | 23 ms | 23800 KB | n=100 |
8 | Correct | 23 ms | 23804 KB | n=100 |
9 | Correct | 22 ms | 23800 KB | n=100 |
10 | Correct | 23 ms | 23800 KB | n=100 |
11 | Correct | 22 ms | 23800 KB | n=100 |
12 | Correct | 23 ms | 23928 KB | n=100 |
13 | Correct | 22 ms | 23800 KB | n=100 |
14 | Correct | 23 ms | 23800 KB | n=100 |
15 | Correct | 23 ms | 23800 KB | n=100 |
16 | Correct | 23 ms | 23800 KB | n=100 |
17 | Correct | 23 ms | 23880 KB | n=100 |
18 | Correct | 23 ms | 23928 KB | n=100 |
19 | Correct | 23 ms | 23800 KB | n=100 |
20 | Correct | 23 ms | 23800 KB | n=100 |
21 | Correct | 22 ms | 23800 KB | n=100 |
22 | Correct | 23 ms | 23800 KB | n=100 |
23 | Correct | 23 ms | 23800 KB | n=100 |
24 | Correct | 23 ms | 23800 KB | n=100 |
25 | Correct | 22 ms | 23928 KB | n=100 |
26 | Correct | 23 ms | 23800 KB | n=12 |
27 | Correct | 23 ms | 23800 KB | n=100 |
28 | Correct | 23 ms | 23928 KB | n=500 |
29 | Correct | 23 ms | 23928 KB | n=500 |
30 | Correct | 23 ms | 23928 KB | n=500 |
31 | Correct | 24 ms | 23928 KB | n=500 |
32 | Correct | 23 ms | 23928 KB | n=500 |
33 | Correct | 24 ms | 23928 KB | n=500 |
34 | Correct | 23 ms | 23928 KB | n=500 |
35 | Correct | 23 ms | 23928 KB | n=500 |
36 | Correct | 23 ms | 23928 KB | n=500 |
37 | Correct | 23 ms | 23904 KB | n=500 |
38 | Correct | 23 ms | 23928 KB | n=500 |
39 | Correct | 23 ms | 23900 KB | n=500 |
40 | Correct | 27 ms | 23928 KB | n=500 |
41 | Correct | 23 ms | 23928 KB | n=500 |
42 | Correct | 23 ms | 23928 KB | n=500 |
43 | Correct | 29 ms | 23928 KB | n=500 |
44 | Correct | 29 ms | 23928 KB | n=500 |
45 | Correct | 26 ms | 24056 KB | n=500 |
46 | Correct | 24 ms | 23928 KB | n=500 |
47 | Correct | 24 ms | 23976 KB | n=500 |
48 | Correct | 24 ms | 23932 KB | n=500 |
49 | Correct | 30 ms | 23928 KB | n=500 |
50 | Correct | 23 ms | 23928 KB | n=500 |
51 | Correct | 24 ms | 23932 KB | n=500 |
52 | Correct | 24 ms | 23928 KB | n=500 |
53 | Correct | 24 ms | 23928 KB | n=500 |
54 | Correct | 23 ms | 23928 KB | n=500 |
55 | Correct | 23 ms | 23928 KB | n=278 |
56 | Correct | 23 ms | 23928 KB | n=500 |
57 | Correct | 24 ms | 23928 KB | n=500 |
58 | Correct | 23 ms | 23928 KB | n=500 |
59 | Correct | 28 ms | 24316 KB | n=2000 |
60 | Correct | 27 ms | 24444 KB | n=2000 |
61 | Correct | 29 ms | 24568 KB | n=2000 |
62 | Correct | 29 ms | 24312 KB | n=2000 |
63 | Correct | 27 ms | 24312 KB | n=2000 |
64 | Correct | 28 ms | 24428 KB | n=2000 |
65 | Correct | 28 ms | 24312 KB | n=2000 |
66 | Correct | 28 ms | 24440 KB | n=2000 |
67 | Correct | 33 ms | 24284 KB | n=2000 |
68 | Correct | 28 ms | 24312 KB | n=2000 |
69 | Correct | 26 ms | 24312 KB | n=2000 |
70 | Correct | 27 ms | 24312 KB | n=2000 |
71 | Correct | 26 ms | 24312 KB | n=2000 |
72 | Correct | 26 ms | 24312 KB | n=2000 |
73 | Correct | 27 ms | 24284 KB | n=2000 |
74 | Correct | 32 ms | 24312 KB | n=1844 |
75 | Correct | 27 ms | 24312 KB | n=2000 |
76 | Correct | 33 ms | 24312 KB | n=2000 |
77 | Correct | 34 ms | 24372 KB | n=2000 |
78 | Correct | 28 ms | 24312 KB | n=2000 |
79 | Correct | 28 ms | 24312 KB | n=2000 |
80 | Correct | 28 ms | 24312 KB | n=2000 |
81 | Correct | 28 ms | 24312 KB | n=2000 |
82 | Correct | 28 ms | 24312 KB | n=2000 |
83 | Correct | 27 ms | 24440 KB | n=2000 |
84 | Correct | 27 ms | 24316 KB | n=2000 |
85 | Correct | 28 ms | 24440 KB | n=2000 |
86 | Correct | 28 ms | 24312 KB | n=2000 |
87 | Correct | 28 ms | 24312 KB | n=2000 |
88 | Correct | 28 ms | 24440 KB | n=2000 |
89 | Correct | 27 ms | 24440 KB | n=2000 |
90 | Correct | 28 ms | 24440 KB | n=2000 |
91 | Correct | 31 ms | 24312 KB | n=2000 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23800 KB | n=5 |
2 | Correct | 23 ms | 23800 KB | n=100 |
3 | Correct | 22 ms | 23800 KB | n=100 |
4 | Correct | 23 ms | 23800 KB | n=100 |
5 | Correct | 23 ms | 23772 KB | n=100 |
6 | Correct | 22 ms | 23800 KB | n=100 |
7 | Correct | 23 ms | 23800 KB | n=100 |
8 | Correct | 23 ms | 23804 KB | n=100 |
9 | Correct | 22 ms | 23800 KB | n=100 |
10 | Correct | 23 ms | 23800 KB | n=100 |
11 | Correct | 22 ms | 23800 KB | n=100 |
12 | Correct | 23 ms | 23928 KB | n=100 |
13 | Correct | 22 ms | 23800 KB | n=100 |
14 | Correct | 23 ms | 23800 KB | n=100 |
15 | Correct | 23 ms | 23800 KB | n=100 |
16 | Correct | 23 ms | 23800 KB | n=100 |
17 | Correct | 23 ms | 23880 KB | n=100 |
18 | Correct | 23 ms | 23928 KB | n=100 |
19 | Correct | 23 ms | 23800 KB | n=100 |
20 | Correct | 23 ms | 23800 KB | n=100 |
21 | Correct | 22 ms | 23800 KB | n=100 |
22 | Correct | 23 ms | 23800 KB | n=100 |
23 | Correct | 23 ms | 23800 KB | n=100 |
24 | Correct | 23 ms | 23800 KB | n=100 |
25 | Correct | 22 ms | 23928 KB | n=100 |
26 | Correct | 23 ms | 23800 KB | n=12 |
27 | Correct | 23 ms | 23800 KB | n=100 |
28 | Correct | 23 ms | 23928 KB | n=500 |
29 | Correct | 23 ms | 23928 KB | n=500 |
30 | Correct | 23 ms | 23928 KB | n=500 |
31 | Correct | 24 ms | 23928 KB | n=500 |
32 | Correct | 23 ms | 23928 KB | n=500 |
33 | Correct | 24 ms | 23928 KB | n=500 |
34 | Correct | 23 ms | 23928 KB | n=500 |
35 | Correct | 23 ms | 23928 KB | n=500 |
36 | Correct | 23 ms | 23928 KB | n=500 |
37 | Correct | 23 ms | 23904 KB | n=500 |
38 | Correct | 23 ms | 23928 KB | n=500 |
39 | Correct | 23 ms | 23900 KB | n=500 |
40 | Correct | 27 ms | 23928 KB | n=500 |
41 | Correct | 23 ms | 23928 KB | n=500 |
42 | Correct | 23 ms | 23928 KB | n=500 |
43 | Correct | 29 ms | 23928 KB | n=500 |
44 | Correct | 29 ms | 23928 KB | n=500 |
45 | Correct | 26 ms | 24056 KB | n=500 |
46 | Correct | 24 ms | 23928 KB | n=500 |
47 | Correct | 24 ms | 23976 KB | n=500 |
48 | Correct | 24 ms | 23932 KB | n=500 |
49 | Correct | 30 ms | 23928 KB | n=500 |
50 | Correct | 23 ms | 23928 KB | n=500 |
51 | Correct | 24 ms | 23932 KB | n=500 |
52 | Correct | 24 ms | 23928 KB | n=500 |
53 | Correct | 24 ms | 23928 KB | n=500 |
54 | Correct | 23 ms | 23928 KB | n=500 |
55 | Correct | 23 ms | 23928 KB | n=278 |
56 | Correct | 23 ms | 23928 KB | n=500 |
57 | Correct | 24 ms | 23928 KB | n=500 |
58 | Correct | 23 ms | 23928 KB | n=500 |
59 | Correct | 28 ms | 24316 KB | n=2000 |
60 | Correct | 27 ms | 24444 KB | n=2000 |
61 | Correct | 29 ms | 24568 KB | n=2000 |
62 | Correct | 29 ms | 24312 KB | n=2000 |
63 | Correct | 27 ms | 24312 KB | n=2000 |
64 | Correct | 28 ms | 24428 KB | n=2000 |
65 | Correct | 28 ms | 24312 KB | n=2000 |
66 | Correct | 28 ms | 24440 KB | n=2000 |
67 | Correct | 33 ms | 24284 KB | n=2000 |
68 | Correct | 28 ms | 24312 KB | n=2000 |
69 | Correct | 26 ms | 24312 KB | n=2000 |
70 | Correct | 27 ms | 24312 KB | n=2000 |
71 | Correct | 26 ms | 24312 KB | n=2000 |
72 | Correct | 26 ms | 24312 KB | n=2000 |
73 | Correct | 27 ms | 24284 KB | n=2000 |
74 | Correct | 32 ms | 24312 KB | n=1844 |
75 | Correct | 27 ms | 24312 KB | n=2000 |
76 | Correct | 33 ms | 24312 KB | n=2000 |
77 | Correct | 34 ms | 24372 KB | n=2000 |
78 | Correct | 28 ms | 24312 KB | n=2000 |
79 | Correct | 28 ms | 24312 KB | n=2000 |
80 | Correct | 28 ms | 24312 KB | n=2000 |
81 | Correct | 28 ms | 24312 KB | n=2000 |
82 | Correct | 28 ms | 24312 KB | n=2000 |
83 | Correct | 27 ms | 24440 KB | n=2000 |
84 | Correct | 27 ms | 24316 KB | n=2000 |
85 | Correct | 28 ms | 24440 KB | n=2000 |
86 | Correct | 28 ms | 24312 KB | n=2000 |
87 | Correct | 28 ms | 24312 KB | n=2000 |
88 | Correct | 28 ms | 24440 KB | n=2000 |
89 | Correct | 27 ms | 24440 KB | n=2000 |
90 | Correct | 28 ms | 24440 KB | n=2000 |
91 | Correct | 31 ms | 24312 KB | n=2000 |
92 | Correct | 1104 ms | 75484 KB | n=200000 |
93 | Correct | 1457 ms | 80164 KB | n=200000 |
94 | Correct | 1367 ms | 83664 KB | n=200000 |
95 | Correct | 914 ms | 75244 KB | n=200000 |
96 | Correct | 935 ms | 75368 KB | n=200000 |
97 | Correct | 1514 ms | 79612 KB | n=200000 |
98 | Correct | 1016 ms | 75244 KB | n=200000 |
99 | Correct | 1178 ms | 75512 KB | n=200000 |
100 | Correct | 976 ms | 75248 KB | n=200000 |
101 | Correct | 1580 ms | 84868 KB | n=200000 |
102 | Correct | 600 ms | 76536 KB | n=200000 |
103 | Correct | 615 ms | 76512 KB | n=200000 |
104 | Correct | 585 ms | 76488 KB | n=200000 |
105 | Correct | 648 ms | 76796 KB | n=200000 |
106 | Correct | 604 ms | 76920 KB | n=200000 |
107 | Correct | 600 ms | 76792 KB | n=200000 |
108 | Correct | 1253 ms | 75512 KB | n=200000 |
109 | Correct | 1075 ms | 75464 KB | n=200000 |
110 | Correct | 1130 ms | 75384 KB | n=200000 |
111 | Correct | 1006 ms | 74728 KB | n=200000 |
112 | Correct | 1432 ms | 84088 KB | n=200000 |
113 | Correct | 1467 ms | 79308 KB | n=200000 |
114 | Correct | 997 ms | 74984 KB | n=200000 |
115 | Correct | 1590 ms | 77312 KB | n=200000 |
116 | Correct | 951 ms | 75496 KB | n=200000 |
117 | Correct | 1455 ms | 84480 KB | n=200000 |
118 | Correct | 1652 ms | 78348 KB | n=200000 |
119 | Correct | 910 ms | 75468 KB | n=200000 |
120 | Correct | 1391 ms | 84020 KB | n=200000 |
121 | Correct | 1480 ms | 84004 KB | n=200000 |
122 | Correct | 1636 ms | 84344 KB | n=200000 |
123 | Correct | 616 ms | 76784 KB | n=200000 |
124 | Correct | 302 ms | 38904 KB | n=25264 |