# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
89727 | 2018-12-18T08:35:59 Z | mirbek01 | Birthday gift (IZhO18_treearray) | C++17 | 2375 ms | 79308 KB |
# include <bits/stdc++.h> using namespace std; const int N = 2e5 + 2; int n, m, q, a[N]; int p[20][N], tin[N], tout[N], timer; vector <int> g[N]; set <int> s[N], ps[N]; set <int> :: iterator it; void dfs(int v, int pr = 0){ tin[v] = ++ timer; p[0][v] = pr; for(int i = 1; i <= 19; i ++) p[i][v] = p[i - 1][ p[i - 1][v] ]; for(int to : g[v]){ if(to == pr) continue; dfs(to, v); } tout[v] = timer; } bool upper(int a, int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a, int b){ if(upper(a, b)) return a; if(upper(b, a)) return b; for(int i = 19; i >= 0; i --){ if(p[i][a] && !upper(p[i][a], b)) a = p[i][a]; } return p[0][a]; } int main(){ scanf("%d %d %d", &n, &m, &q); for(int i = 1; i < n; i ++){ int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1); for(int i = 1; i <= m; i ++){ scanf("%d", a + i); if(i > 1){ int lc = lca(a[i - 1], a[i]); s[lc].insert(i - 1); } ps[a[i]].insert(i); } while(q --){ int l, r, v, type; scanf("%d", &type); scanf("%d %d", &l, &r); if(type == 1){ ps[ a[l] ].erase(l); ps[ r ].insert(l); if(l + 1 <= m){ int lc = lca(a[l], a[l + 1]); s[lc].erase(l); lc = lca(r, a[l + 1]); s[lc].insert(l); } if(l - 1 >= 1){ int lc = lca(a[l], a[l - 1]); s[lc].erase(l - 1); lc = lca(r, a[l - 1]); s[lc].insert(l - 1); } a[l] = r; } else { scanf("%d", &v); if(l == r){ if(a[l] == v){ cout << l << " " << l << endl; } else { puts("-1 -1"); } } else { if(!ps[v].empty()){ it = ps[v].lower_bound(l); if(it != ps[v].end() && (*it) <= r){ cout << (*it) << " " << (*it) << endl; continue; } } if(s[v].empty()){ puts("-1 -1"); continue; } it = s[v].lower_bound(l); if(it == s[v].end() || (*it) >= r){ puts("-1 -1"); continue; } cout << *it << " " << (*it) + 1 << endl; } } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 23928 KB | n=5 |
2 | Correct | 25 ms | 23932 KB | n=100 |
3 | Correct | 25 ms | 24104 KB | n=100 |
4 | Correct | 25 ms | 24104 KB | n=100 |
5 | Correct | 26 ms | 24104 KB | n=100 |
6 | Correct | 25 ms | 24108 KB | n=100 |
7 | Correct | 27 ms | 24156 KB | n=100 |
8 | Correct | 25 ms | 24212 KB | n=100 |
9 | Correct | 26 ms | 24212 KB | n=100 |
10 | Correct | 26 ms | 24212 KB | n=100 |
11 | Correct | 25 ms | 24212 KB | n=100 |
12 | Correct | 25 ms | 24212 KB | n=100 |
13 | Correct | 25 ms | 24212 KB | n=100 |
14 | Correct | 25 ms | 24212 KB | n=100 |
15 | Correct | 24 ms | 24212 KB | n=100 |
16 | Correct | 27 ms | 24212 KB | n=100 |
17 | Correct | 26 ms | 24212 KB | n=100 |
18 | Correct | 25 ms | 24212 KB | n=100 |
19 | Correct | 26 ms | 24332 KB | n=100 |
20 | Correct | 26 ms | 24332 KB | n=100 |
21 | Correct | 23 ms | 24332 KB | n=100 |
22 | Correct | 22 ms | 24332 KB | n=100 |
23 | Correct | 22 ms | 24332 KB | n=100 |
24 | Correct | 22 ms | 24332 KB | n=100 |
25 | Correct | 22 ms | 24332 KB | n=100 |
26 | Correct | 22 ms | 24332 KB | n=12 |
27 | Correct | 22 ms | 24332 KB | n=100 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 23928 KB | n=5 |
2 | Correct | 25 ms | 23932 KB | n=100 |
3 | Correct | 25 ms | 24104 KB | n=100 |
4 | Correct | 25 ms | 24104 KB | n=100 |
5 | Correct | 26 ms | 24104 KB | n=100 |
6 | Correct | 25 ms | 24108 KB | n=100 |
7 | Correct | 27 ms | 24156 KB | n=100 |
8 | Correct | 25 ms | 24212 KB | n=100 |
9 | Correct | 26 ms | 24212 KB | n=100 |
10 | Correct | 26 ms | 24212 KB | n=100 |
11 | Correct | 25 ms | 24212 KB | n=100 |
12 | Correct | 25 ms | 24212 KB | n=100 |
13 | Correct | 25 ms | 24212 KB | n=100 |
14 | Correct | 25 ms | 24212 KB | n=100 |
15 | Correct | 24 ms | 24212 KB | n=100 |
16 | Correct | 27 ms | 24212 KB | n=100 |
17 | Correct | 26 ms | 24212 KB | n=100 |
18 | Correct | 25 ms | 24212 KB | n=100 |
19 | Correct | 26 ms | 24332 KB | n=100 |
20 | Correct | 26 ms | 24332 KB | n=100 |
21 | Correct | 23 ms | 24332 KB | n=100 |
22 | Correct | 22 ms | 24332 KB | n=100 |
23 | Correct | 22 ms | 24332 KB | n=100 |
24 | Correct | 22 ms | 24332 KB | n=100 |
25 | Correct | 22 ms | 24332 KB | n=100 |
26 | Correct | 22 ms | 24332 KB | n=12 |
27 | Correct | 22 ms | 24332 KB | n=100 |
28 | Correct | 23 ms | 24400 KB | n=500 |
29 | Correct | 22 ms | 24404 KB | n=500 |
30 | Correct | 26 ms | 24404 KB | n=500 |
31 | Correct | 23 ms | 24404 KB | n=500 |
32 | Correct | 23 ms | 24484 KB | n=500 |
33 | Correct | 23 ms | 24484 KB | n=500 |
34 | Correct | 22 ms | 24484 KB | n=500 |
35 | Correct | 22 ms | 24484 KB | n=500 |
36 | Correct | 24 ms | 24484 KB | n=500 |
37 | Correct | 27 ms | 24484 KB | n=500 |
38 | Correct | 27 ms | 24484 KB | n=500 |
39 | Correct | 26 ms | 24484 KB | n=500 |
40 | Correct | 26 ms | 24484 KB | n=500 |
41 | Correct | 26 ms | 24484 KB | n=500 |
42 | Correct | 27 ms | 24516 KB | n=500 |
43 | Correct | 23 ms | 24516 KB | n=500 |
44 | Correct | 26 ms | 24516 KB | n=500 |
45 | Correct | 24 ms | 24516 KB | n=500 |
46 | Correct | 23 ms | 24516 KB | n=500 |
47 | Correct | 21 ms | 24516 KB | n=500 |
48 | Correct | 23 ms | 24532 KB | n=500 |
49 | Correct | 24 ms | 24664 KB | n=500 |
50 | Correct | 23 ms | 24664 KB | n=500 |
51 | Correct | 22 ms | 24664 KB | n=500 |
52 | Correct | 23 ms | 24664 KB | n=500 |
53 | Correct | 22 ms | 24664 KB | n=500 |
54 | Correct | 22 ms | 24664 KB | n=500 |
55 | Correct | 22 ms | 24664 KB | n=278 |
56 | Correct | 23 ms | 24664 KB | n=500 |
57 | Correct | 24 ms | 24708 KB | n=500 |
58 | Correct | 27 ms | 24708 KB | n=500 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 23928 KB | n=5 |
2 | Correct | 25 ms | 23932 KB | n=100 |
3 | Correct | 25 ms | 24104 KB | n=100 |
4 | Correct | 25 ms | 24104 KB | n=100 |
5 | Correct | 26 ms | 24104 KB | n=100 |
6 | Correct | 25 ms | 24108 KB | n=100 |
7 | Correct | 27 ms | 24156 KB | n=100 |
8 | Correct | 25 ms | 24212 KB | n=100 |
9 | Correct | 26 ms | 24212 KB | n=100 |
10 | Correct | 26 ms | 24212 KB | n=100 |
11 | Correct | 25 ms | 24212 KB | n=100 |
12 | Correct | 25 ms | 24212 KB | n=100 |
13 | Correct | 25 ms | 24212 KB | n=100 |
14 | Correct | 25 ms | 24212 KB | n=100 |
15 | Correct | 24 ms | 24212 KB | n=100 |
16 | Correct | 27 ms | 24212 KB | n=100 |
17 | Correct | 26 ms | 24212 KB | n=100 |
18 | Correct | 25 ms | 24212 KB | n=100 |
19 | Correct | 26 ms | 24332 KB | n=100 |
20 | Correct | 26 ms | 24332 KB | n=100 |
21 | Correct | 23 ms | 24332 KB | n=100 |
22 | Correct | 22 ms | 24332 KB | n=100 |
23 | Correct | 22 ms | 24332 KB | n=100 |
24 | Correct | 22 ms | 24332 KB | n=100 |
25 | Correct | 22 ms | 24332 KB | n=100 |
26 | Correct | 22 ms | 24332 KB | n=12 |
27 | Correct | 22 ms | 24332 KB | n=100 |
28 | Correct | 23 ms | 24400 KB | n=500 |
29 | Correct | 22 ms | 24404 KB | n=500 |
30 | Correct | 26 ms | 24404 KB | n=500 |
31 | Correct | 23 ms | 24404 KB | n=500 |
32 | Correct | 23 ms | 24484 KB | n=500 |
33 | Correct | 23 ms | 24484 KB | n=500 |
34 | Correct | 22 ms | 24484 KB | n=500 |
35 | Correct | 22 ms | 24484 KB | n=500 |
36 | Correct | 24 ms | 24484 KB | n=500 |
37 | Correct | 27 ms | 24484 KB | n=500 |
38 | Correct | 27 ms | 24484 KB | n=500 |
39 | Correct | 26 ms | 24484 KB | n=500 |
40 | Correct | 26 ms | 24484 KB | n=500 |
41 | Correct | 26 ms | 24484 KB | n=500 |
42 | Correct | 27 ms | 24516 KB | n=500 |
43 | Correct | 23 ms | 24516 KB | n=500 |
44 | Correct | 26 ms | 24516 KB | n=500 |
45 | Correct | 24 ms | 24516 KB | n=500 |
46 | Correct | 23 ms | 24516 KB | n=500 |
47 | Correct | 21 ms | 24516 KB | n=500 |
48 | Correct | 23 ms | 24532 KB | n=500 |
49 | Correct | 24 ms | 24664 KB | n=500 |
50 | Correct | 23 ms | 24664 KB | n=500 |
51 | Correct | 22 ms | 24664 KB | n=500 |
52 | Correct | 23 ms | 24664 KB | n=500 |
53 | Correct | 22 ms | 24664 KB | n=500 |
54 | Correct | 22 ms | 24664 KB | n=500 |
55 | Correct | 22 ms | 24664 KB | n=278 |
56 | Correct | 23 ms | 24664 KB | n=500 |
57 | Correct | 24 ms | 24708 KB | n=500 |
58 | Correct | 27 ms | 24708 KB | n=500 |
59 | Correct | 32 ms | 25056 KB | n=2000 |
60 | Correct | 30 ms | 25236 KB | n=2000 |
61 | Correct | 31 ms | 25236 KB | n=2000 |
62 | Correct | 32 ms | 25260 KB | n=2000 |
63 | Correct | 31 ms | 25260 KB | n=2000 |
64 | Correct | 30 ms | 25268 KB | n=2000 |
65 | Correct | 30 ms | 25276 KB | n=2000 |
66 | Correct | 31 ms | 25292 KB | n=2000 |
67 | Correct | 31 ms | 25292 KB | n=2000 |
68 | Correct | 31 ms | 25292 KB | n=2000 |
69 | Correct | 32 ms | 25292 KB | n=2000 |
70 | Correct | 32 ms | 25292 KB | n=2000 |
71 | Correct | 28 ms | 25292 KB | n=2000 |
72 | Correct | 25 ms | 25292 KB | n=2000 |
73 | Correct | 25 ms | 25292 KB | n=2000 |
74 | Correct | 26 ms | 25292 KB | n=1844 |
75 | Correct | 29 ms | 25292 KB | n=2000 |
76 | Correct | 28 ms | 25292 KB | n=2000 |
77 | Correct | 32 ms | 25292 KB | n=2000 |
78 | Correct | 32 ms | 25292 KB | n=2000 |
79 | Correct | 30 ms | 25292 KB | n=2000 |
80 | Correct | 31 ms | 25292 KB | n=2000 |
81 | Correct | 32 ms | 25292 KB | n=2000 |
82 | Correct | 31 ms | 25292 KB | n=2000 |
83 | Correct | 30 ms | 25292 KB | n=2000 |
84 | Correct | 30 ms | 25292 KB | n=2000 |
85 | Correct | 30 ms | 25292 KB | n=2000 |
86 | Correct | 30 ms | 25292 KB | n=2000 |
87 | Correct | 30 ms | 25292 KB | n=2000 |
88 | Correct | 29 ms | 25296 KB | n=2000 |
89 | Correct | 29 ms | 25300 KB | n=2000 |
90 | Correct | 30 ms | 25300 KB | n=2000 |
91 | Correct | 31 ms | 25300 KB | n=2000 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 23928 KB | n=5 |
2 | Correct | 25 ms | 23932 KB | n=100 |
3 | Correct | 25 ms | 24104 KB | n=100 |
4 | Correct | 25 ms | 24104 KB | n=100 |
5 | Correct | 26 ms | 24104 KB | n=100 |
6 | Correct | 25 ms | 24108 KB | n=100 |
7 | Correct | 27 ms | 24156 KB | n=100 |
8 | Correct | 25 ms | 24212 KB | n=100 |
9 | Correct | 26 ms | 24212 KB | n=100 |
10 | Correct | 26 ms | 24212 KB | n=100 |
11 | Correct | 25 ms | 24212 KB | n=100 |
12 | Correct | 25 ms | 24212 KB | n=100 |
13 | Correct | 25 ms | 24212 KB | n=100 |
14 | Correct | 25 ms | 24212 KB | n=100 |
15 | Correct | 24 ms | 24212 KB | n=100 |
16 | Correct | 27 ms | 24212 KB | n=100 |
17 | Correct | 26 ms | 24212 KB | n=100 |
18 | Correct | 25 ms | 24212 KB | n=100 |
19 | Correct | 26 ms | 24332 KB | n=100 |
20 | Correct | 26 ms | 24332 KB | n=100 |
21 | Correct | 23 ms | 24332 KB | n=100 |
22 | Correct | 22 ms | 24332 KB | n=100 |
23 | Correct | 22 ms | 24332 KB | n=100 |
24 | Correct | 22 ms | 24332 KB | n=100 |
25 | Correct | 22 ms | 24332 KB | n=100 |
26 | Correct | 22 ms | 24332 KB | n=12 |
27 | Correct | 22 ms | 24332 KB | n=100 |
28 | Correct | 23 ms | 24400 KB | n=500 |
29 | Correct | 22 ms | 24404 KB | n=500 |
30 | Correct | 26 ms | 24404 KB | n=500 |
31 | Correct | 23 ms | 24404 KB | n=500 |
32 | Correct | 23 ms | 24484 KB | n=500 |
33 | Correct | 23 ms | 24484 KB | n=500 |
34 | Correct | 22 ms | 24484 KB | n=500 |
35 | Correct | 22 ms | 24484 KB | n=500 |
36 | Correct | 24 ms | 24484 KB | n=500 |
37 | Correct | 27 ms | 24484 KB | n=500 |
38 | Correct | 27 ms | 24484 KB | n=500 |
39 | Correct | 26 ms | 24484 KB | n=500 |
40 | Correct | 26 ms | 24484 KB | n=500 |
41 | Correct | 26 ms | 24484 KB | n=500 |
42 | Correct | 27 ms | 24516 KB | n=500 |
43 | Correct | 23 ms | 24516 KB | n=500 |
44 | Correct | 26 ms | 24516 KB | n=500 |
45 | Correct | 24 ms | 24516 KB | n=500 |
46 | Correct | 23 ms | 24516 KB | n=500 |
47 | Correct | 21 ms | 24516 KB | n=500 |
48 | Correct | 23 ms | 24532 KB | n=500 |
49 | Correct | 24 ms | 24664 KB | n=500 |
50 | Correct | 23 ms | 24664 KB | n=500 |
51 | Correct | 22 ms | 24664 KB | n=500 |
52 | Correct | 23 ms | 24664 KB | n=500 |
53 | Correct | 22 ms | 24664 KB | n=500 |
54 | Correct | 22 ms | 24664 KB | n=500 |
55 | Correct | 22 ms | 24664 KB | n=278 |
56 | Correct | 23 ms | 24664 KB | n=500 |
57 | Correct | 24 ms | 24708 KB | n=500 |
58 | Correct | 27 ms | 24708 KB | n=500 |
59 | Correct | 32 ms | 25056 KB | n=2000 |
60 | Correct | 30 ms | 25236 KB | n=2000 |
61 | Correct | 31 ms | 25236 KB | n=2000 |
62 | Correct | 32 ms | 25260 KB | n=2000 |
63 | Correct | 31 ms | 25260 KB | n=2000 |
64 | Correct | 30 ms | 25268 KB | n=2000 |
65 | Correct | 30 ms | 25276 KB | n=2000 |
66 | Correct | 31 ms | 25292 KB | n=2000 |
67 | Correct | 31 ms | 25292 KB | n=2000 |
68 | Correct | 31 ms | 25292 KB | n=2000 |
69 | Correct | 32 ms | 25292 KB | n=2000 |
70 | Correct | 32 ms | 25292 KB | n=2000 |
71 | Correct | 28 ms | 25292 KB | n=2000 |
72 | Correct | 25 ms | 25292 KB | n=2000 |
73 | Correct | 25 ms | 25292 KB | n=2000 |
74 | Correct | 26 ms | 25292 KB | n=1844 |
75 | Correct | 29 ms | 25292 KB | n=2000 |
76 | Correct | 28 ms | 25292 KB | n=2000 |
77 | Correct | 32 ms | 25292 KB | n=2000 |
78 | Correct | 32 ms | 25292 KB | n=2000 |
79 | Correct | 30 ms | 25292 KB | n=2000 |
80 | Correct | 31 ms | 25292 KB | n=2000 |
81 | Correct | 32 ms | 25292 KB | n=2000 |
82 | Correct | 31 ms | 25292 KB | n=2000 |
83 | Correct | 30 ms | 25292 KB | n=2000 |
84 | Correct | 30 ms | 25292 KB | n=2000 |
85 | Correct | 30 ms | 25292 KB | n=2000 |
86 | Correct | 30 ms | 25292 KB | n=2000 |
87 | Correct | 30 ms | 25292 KB | n=2000 |
88 | Correct | 29 ms | 25296 KB | n=2000 |
89 | Correct | 29 ms | 25300 KB | n=2000 |
90 | Correct | 30 ms | 25300 KB | n=2000 |
91 | Correct | 31 ms | 25300 KB | n=2000 |
92 | Correct | 1398 ms | 70208 KB | n=200000 |
93 | Correct | 1511 ms | 73996 KB | n=200000 |
94 | Correct | 1014 ms | 77344 KB | n=200000 |
95 | Correct | 1151 ms | 77344 KB | n=200000 |
96 | Correct | 1130 ms | 77344 KB | n=200000 |
97 | Correct | 1612 ms | 77344 KB | n=200000 |
98 | Correct | 1295 ms | 77344 KB | n=200000 |
99 | Correct | 1372 ms | 77344 KB | n=200000 |
100 | Correct | 1423 ms | 77344 KB | n=200000 |
101 | Correct | 1006 ms | 78708 KB | n=200000 |
102 | Correct | 1043 ms | 78708 KB | n=200000 |
103 | Correct | 1018 ms | 78708 KB | n=200000 |
104 | Correct | 1002 ms | 78708 KB | n=200000 |
105 | Correct | 972 ms | 78708 KB | n=200000 |
106 | Correct | 914 ms | 78708 KB | n=200000 |
107 | Correct | 1069 ms | 78708 KB | n=200000 |
108 | Correct | 1455 ms | 78708 KB | n=200000 |
109 | Correct | 1478 ms | 78708 KB | n=200000 |
110 | Correct | 1543 ms | 78708 KB | n=200000 |
111 | Correct | 1380 ms | 78708 KB | n=200000 |
112 | Correct | 1108 ms | 78708 KB | n=200000 |
113 | Correct | 1769 ms | 78708 KB | n=200000 |
114 | Correct | 1392 ms | 78708 KB | n=200000 |
115 | Correct | 2375 ms | 78708 KB | n=200000 |
116 | Correct | 1267 ms | 78708 KB | n=200000 |
117 | Correct | 959 ms | 78708 KB | n=200000 |
118 | Correct | 2148 ms | 78708 KB | n=200000 |
119 | Correct | 1277 ms | 78708 KB | n=200000 |
120 | Correct | 800 ms | 78896 KB | n=200000 |
121 | Correct | 839 ms | 78900 KB | n=200000 |
122 | Correct | 952 ms | 79308 KB | n=200000 |
123 | Correct | 932 ms | 79308 KB | n=200000 |
124 | Correct | 362 ms | 79308 KB | n=25264 |