답안 #92366 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92366	2019-01-02T16:08:24 Z	Nodir_Bobiev	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4000 ms	22492 KB

treearray

# include <iostream>
# include <vector>

using namespace std;

const int N = 2e5 + 100;

int n, m, q;
int p[N];
int g[N] = {-1};
int a[N];
vector < int > gr[N];

void dfs(int v, int f)
{
	g[v] = g[f] + 1;
	p[v] = f;
	for(auto to: gr[v])
		if(to != f)
			dfs(to, v);
}

int lca(int v, int u)
{
	if(g[v] > g[u]) return lca(p[v], u);
	if(g[v] < g[u]) return lca(v, p[u]);
	if(v != u) return lca(p[v], u);
	return v;
}

int main()
{
	
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		gr[v].push_back(u);
		gr[u].push_back(v);
	}
	
	for (int i = 1; i <= m; i++)
		cin >> a[i];
	
	dfs(1, 0);
		
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, v;
			cin >> pos >> v;
			a[pos] = v;
		}
		else{
			int l, r, v, l1 = -1, r1 = -1;
			cin >> l >> r >> v;
			//cout << l << ' ' << r << ' ' << v << endl;
			for (int x = l; x <= r; x++){
				//cout << '\t' << lca(a[x], a[x + 1]) << endl;
				if(x != r && lca(a[x], a[x + 1]) == v){
					l1 = x; r1 = x + 1;
					break;
				}
				else if(a[x] == v){
					l1 = x; r1 = x;
					break;
				}
			}
			cout << l1 << ' ' << r1 << endl;
		}
	}
}

/*

5 4 4
1 2
3 1
3 4
5 3
4 5 2 3 
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

*/

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	n=5
2	Correct	6 ms	5112 KB	n=100
3	Correct	6 ms	4984 KB	n=100
4	Correct	6 ms	5112 KB	n=100
5	Correct	6 ms	4984 KB	n=100
6	Correct	6 ms	5116 KB	n=100
7	Correct	6 ms	4984 KB	n=100
8	Correct	6 ms	4984 KB	n=100
9	Correct	6 ms	4984 KB	n=100
10	Correct	6 ms	5112 KB	n=100
11	Correct	6 ms	4988 KB	n=100
12	Correct	6 ms	5112 KB	n=100
13	Correct	6 ms	5112 KB	n=100
14	Correct	6 ms	4984 KB	n=100
15	Correct	6 ms	5112 KB	n=100
16	Correct	6 ms	5112 KB	n=100
17	Correct	6 ms	4984 KB	n=100
18	Correct	6 ms	4984 KB	n=100
19	Correct	6 ms	5112 KB	n=100
20	Correct	6 ms	5112 KB	n=100
21	Correct	6 ms	5112 KB	n=100
22	Correct	6 ms	4984 KB	n=100
23	Correct	6 ms	5116 KB	n=100
24	Correct	6 ms	4984 KB	n=100
25	Correct	6 ms	4984 KB	n=100
26	Correct	6 ms	4984 KB	n=12
27	Correct	6 ms	4984 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	n=5
2	Correct	6 ms	5112 KB	n=100
3	Correct	6 ms	4984 KB	n=100
4	Correct	6 ms	5112 KB	n=100
5	Correct	6 ms	4984 KB	n=100
6	Correct	6 ms	5116 KB	n=100
7	Correct	6 ms	4984 KB	n=100
8	Correct	6 ms	4984 KB	n=100
9	Correct	6 ms	4984 KB	n=100
10	Correct	6 ms	5112 KB	n=100
11	Correct	6 ms	4988 KB	n=100
12	Correct	6 ms	5112 KB	n=100
13	Correct	6 ms	5112 KB	n=100
14	Correct	6 ms	4984 KB	n=100
15	Correct	6 ms	5112 KB	n=100
16	Correct	6 ms	5112 KB	n=100
17	Correct	6 ms	4984 KB	n=100
18	Correct	6 ms	4984 KB	n=100
19	Correct	6 ms	5112 KB	n=100
20	Correct	6 ms	5112 KB	n=100
21	Correct	6 ms	5112 KB	n=100
22	Correct	6 ms	4984 KB	n=100
23	Correct	6 ms	5116 KB	n=100
24	Correct	6 ms	4984 KB	n=100
25	Correct	6 ms	4984 KB	n=100
26	Correct	6 ms	4984 KB	n=12
27	Correct	6 ms	4984 KB	n=100
28	Correct	6 ms	4984 KB	n=500
29	Correct	15 ms	5112 KB	n=500
30	Correct	10 ms	5116 KB	n=500
31	Correct	12 ms	4984 KB	n=500
32	Correct	7 ms	5112 KB	n=500
33	Correct	8 ms	5112 KB	n=500
34	Correct	7 ms	5112 KB	n=500
35	Correct	13 ms	5112 KB	n=500
36	Correct	10 ms	4984 KB	n=500
37	Correct	10 ms	5112 KB	n=500
38	Correct	11 ms	5112 KB	n=500
39	Correct	9 ms	5112 KB	n=500
40	Correct	9 ms	5112 KB	n=500
41	Correct	9 ms	4988 KB	n=500
42	Correct	8 ms	4984 KB	n=500
43	Correct	8 ms	4984 KB	n=500
44	Correct	7 ms	4984 KB	n=500
45	Correct	6 ms	4984 KB	n=500
46	Correct	13 ms	5112 KB	n=500
47	Correct	12 ms	5112 KB	n=500
48	Correct	6 ms	4984 KB	n=500
49	Correct	12 ms	5112 KB	n=500
50	Correct	6 ms	4984 KB	n=500
51	Correct	13 ms	5112 KB	n=500
52	Correct	20 ms	5112 KB	n=500
53	Correct	11 ms	5112 KB	n=500
54	Correct	27 ms	5112 KB	n=500
55	Correct	7 ms	5024 KB	n=278
56	Correct	42 ms	5112 KB	n=500
57	Correct	44 ms	5112 KB	n=500
58	Correct	8 ms	5112 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	n=5
2	Correct	6 ms	5112 KB	n=100
3	Correct	6 ms	4984 KB	n=100
4	Correct	6 ms	5112 KB	n=100
5	Correct	6 ms	4984 KB	n=100
6	Correct	6 ms	5116 KB	n=100
7	Correct	6 ms	4984 KB	n=100
8	Correct	6 ms	4984 KB	n=100
9	Correct	6 ms	4984 KB	n=100
10	Correct	6 ms	5112 KB	n=100
11	Correct	6 ms	4988 KB	n=100
12	Correct	6 ms	5112 KB	n=100
13	Correct	6 ms	5112 KB	n=100
14	Correct	6 ms	4984 KB	n=100
15	Correct	6 ms	5112 KB	n=100
16	Correct	6 ms	5112 KB	n=100
17	Correct	6 ms	4984 KB	n=100
18	Correct	6 ms	4984 KB	n=100
19	Correct	6 ms	5112 KB	n=100
20	Correct	6 ms	5112 KB	n=100
21	Correct	6 ms	5112 KB	n=100
22	Correct	6 ms	4984 KB	n=100
23	Correct	6 ms	5116 KB	n=100
24	Correct	6 ms	4984 KB	n=100
25	Correct	6 ms	4984 KB	n=100
26	Correct	6 ms	4984 KB	n=12
27	Correct	6 ms	4984 KB	n=100
28	Correct	6 ms	4984 KB	n=500
29	Correct	15 ms	5112 KB	n=500
30	Correct	10 ms	5116 KB	n=500
31	Correct	12 ms	4984 KB	n=500
32	Correct	7 ms	5112 KB	n=500
33	Correct	8 ms	5112 KB	n=500
34	Correct	7 ms	5112 KB	n=500
35	Correct	13 ms	5112 KB	n=500
36	Correct	10 ms	4984 KB	n=500
37	Correct	10 ms	5112 KB	n=500
38	Correct	11 ms	5112 KB	n=500
39	Correct	9 ms	5112 KB	n=500
40	Correct	9 ms	5112 KB	n=500
41	Correct	9 ms	4988 KB	n=500
42	Correct	8 ms	4984 KB	n=500
43	Correct	8 ms	4984 KB	n=500
44	Correct	7 ms	4984 KB	n=500
45	Correct	6 ms	4984 KB	n=500
46	Correct	13 ms	5112 KB	n=500
47	Correct	12 ms	5112 KB	n=500
48	Correct	6 ms	4984 KB	n=500
49	Correct	12 ms	5112 KB	n=500
50	Correct	6 ms	4984 KB	n=500
51	Correct	13 ms	5112 KB	n=500
52	Correct	20 ms	5112 KB	n=500
53	Correct	11 ms	5112 KB	n=500
54	Correct	27 ms	5112 KB	n=500
55	Correct	7 ms	5024 KB	n=278
56	Correct	42 ms	5112 KB	n=500
57	Correct	44 ms	5112 KB	n=500
58	Correct	8 ms	5112 KB	n=500
59	Correct	10 ms	5112 KB	n=2000
60	Correct	436 ms	5264 KB	n=2000
61	Correct	240 ms	5240 KB	n=2000
62	Correct	80 ms	5112 KB	n=2000
63	Correct	11 ms	5112 KB	n=2000
64	Correct	139 ms	5240 KB	n=2000
65	Correct	10 ms	5112 KB	n=2000
66	Correct	341 ms	5248 KB	n=2000
67	Correct	11 ms	5112 KB	n=2000
68	Correct	181 ms	5224 KB	n=2000
69	Correct	97 ms	5112 KB	n=2000
70	Correct	94 ms	5112 KB	n=2000
71	Correct	93 ms	5112 KB	n=2000
72	Correct	55 ms	5180 KB	n=2000
73	Correct	53 ms	5184 KB	n=2000
74	Correct	10 ms	5112 KB	n=1844
75	Correct	55 ms	5112 KB	n=2000
76	Correct	50 ms	5112 KB	n=2000
77	Correct	51 ms	5112 KB	n=2000
78	Correct	51 ms	5112 KB	n=2000
79	Correct	10 ms	5116 KB	n=2000
80	Correct	308 ms	5240 KB	n=2000
81	Correct	131 ms	5240 KB	n=2000
82	Correct	10 ms	5112 KB	n=2000
83	Correct	255 ms	5340 KB	n=2000
84	Correct	16 ms	5112 KB	n=2000
85	Correct	228 ms	5112 KB	n=2000
86	Correct	194 ms	5112 KB	n=2000
87	Correct	16 ms	5112 KB	n=2000
88	Correct	2374 ms	5264 KB	n=2000
89	Correct	2389 ms	5368 KB	n=2000
90	Correct	1197 ms	5368 KB	n=2000
91	Correct	64 ms	5112 KB	n=2000

Subtask #4
0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	n=5
2	Correct	6 ms	5112 KB	n=100
3	Correct	6 ms	4984 KB	n=100
4	Correct	6 ms	5112 KB	n=100
5	Correct	6 ms	4984 KB	n=100
6	Correct	6 ms	5116 KB	n=100
7	Correct	6 ms	4984 KB	n=100
8	Correct	6 ms	4984 KB	n=100
9	Correct	6 ms	4984 KB	n=100
10	Correct	6 ms	5112 KB	n=100
11	Correct	6 ms	4988 KB	n=100
12	Correct	6 ms	5112 KB	n=100
13	Correct	6 ms	5112 KB	n=100
14	Correct	6 ms	4984 KB	n=100
15	Correct	6 ms	5112 KB	n=100
16	Correct	6 ms	5112 KB	n=100
17	Correct	6 ms	4984 KB	n=100
18	Correct	6 ms	4984 KB	n=100
19	Correct	6 ms	5112 KB	n=100
20	Correct	6 ms	5112 KB	n=100
21	Correct	6 ms	5112 KB	n=100
22	Correct	6 ms	4984 KB	n=100
23	Correct	6 ms	5116 KB	n=100
24	Correct	6 ms	4984 KB	n=100
25	Correct	6 ms	4984 KB	n=100
26	Correct	6 ms	4984 KB	n=12
27	Correct	6 ms	4984 KB	n=100
28	Correct	6 ms	4984 KB	n=500
29	Correct	15 ms	5112 KB	n=500
30	Correct	10 ms	5116 KB	n=500
31	Correct	12 ms	4984 KB	n=500
32	Correct	7 ms	5112 KB	n=500
33	Correct	8 ms	5112 KB	n=500
34	Correct	7 ms	5112 KB	n=500
35	Correct	13 ms	5112 KB	n=500
36	Correct	10 ms	4984 KB	n=500
37	Correct	10 ms	5112 KB	n=500
38	Correct	11 ms	5112 KB	n=500
39	Correct	9 ms	5112 KB	n=500
40	Correct	9 ms	5112 KB	n=500
41	Correct	9 ms	4988 KB	n=500
42	Correct	8 ms	4984 KB	n=500
43	Correct	8 ms	4984 KB	n=500
44	Correct	7 ms	4984 KB	n=500
45	Correct	6 ms	4984 KB	n=500
46	Correct	13 ms	5112 KB	n=500
47	Correct	12 ms	5112 KB	n=500
48	Correct	6 ms	4984 KB	n=500
49	Correct	12 ms	5112 KB	n=500
50	Correct	6 ms	4984 KB	n=500
51	Correct	13 ms	5112 KB	n=500
52	Correct	20 ms	5112 KB	n=500
53	Correct	11 ms	5112 KB	n=500
54	Correct	27 ms	5112 KB	n=500
55	Correct	7 ms	5024 KB	n=278
56	Correct	42 ms	5112 KB	n=500
57	Correct	44 ms	5112 KB	n=500
58	Correct	8 ms	5112 KB	n=500
59	Correct	10 ms	5112 KB	n=2000
60	Correct	436 ms	5264 KB	n=2000
61	Correct	240 ms	5240 KB	n=2000
62	Correct	80 ms	5112 KB	n=2000
63	Correct	11 ms	5112 KB	n=2000
64	Correct	139 ms	5240 KB	n=2000
65	Correct	10 ms	5112 KB	n=2000
66	Correct	341 ms	5248 KB	n=2000
67	Correct	11 ms	5112 KB	n=2000
68	Correct	181 ms	5224 KB	n=2000
69	Correct	97 ms	5112 KB	n=2000
70	Correct	94 ms	5112 KB	n=2000
71	Correct	93 ms	5112 KB	n=2000
72	Correct	55 ms	5180 KB	n=2000
73	Correct	53 ms	5184 KB	n=2000
74	Correct	10 ms	5112 KB	n=1844
75	Correct	55 ms	5112 KB	n=2000
76	Correct	50 ms	5112 KB	n=2000
77	Correct	51 ms	5112 KB	n=2000
78	Correct	51 ms	5112 KB	n=2000
79	Correct	10 ms	5116 KB	n=2000
80	Correct	308 ms	5240 KB	n=2000
81	Correct	131 ms	5240 KB	n=2000
82	Correct	10 ms	5112 KB	n=2000
83	Correct	255 ms	5340 KB	n=2000
84	Correct	16 ms	5112 KB	n=2000
85	Correct	228 ms	5112 KB	n=2000
86	Correct	194 ms	5112 KB	n=2000
87	Correct	16 ms	5112 KB	n=2000
88	Correct	2374 ms	5264 KB	n=2000
89	Correct	2389 ms	5368 KB	n=2000
90	Correct	1197 ms	5368 KB	n=2000
91	Correct	64 ms	5112 KB	n=2000
92	Correct	624 ms	22008 KB	n=200000
93	Execution timed out	4078 ms	22492 KB	Time limit exceeded
94	Halted	0 ms	0 KB	-

답안 #92366

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 44.0