답안 #41687 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41687	2018-02-20T16:09:37 Z	IvanC	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4000 ms	34972 KB

treearray

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAXN = 2*1e5 + 10;
vector<int> grafo[MAXN];
int ini[MAXN],dfsNum,treearray[MAXN],n,m,q;
ii vetorzao[2*MAXN],seg[8*MAXN];
void dfs(int v,int p,int depth){
	ini[v] = ++dfsNum;
	vetorzao[dfsNum] = ii(depth,v);
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs(u,v,depth+1);
		vetorzao[++dfsNum] = ii(depth,v);
	}
}
void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetorzao[left];
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = min(seg[2*pos],seg[2*pos+1]);
}
ii query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return min(query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j)); 
}
ii func(int l,int r){
	if(l > r) swap(l,r);
	return query(1,1,dfsNum,l,r);
}
int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i = 1;i<n;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	dfs(1,-1,0);
	build(1,1,dfsNum);
	for(int i = 1;i<=m;i++){
		scanf("%d",&treearray[i]);
		treearray[i] = ini[treearray[i]];
	}
	for(int pergunta = 1;pergunta<=q;pergunta++){
		int operacao;
		scanf("%d",&operacao);
		if(operacao == 1){
			int idx,v;
			scanf("%d %d",&idx,&v);
			treearray[idx] = ini[v];
		}
		else{
			int l,r,v,flag = 0;
			scanf("%d %d %d",&l,&r,&v);
			for(int i = l;i<=r && !flag;i++){
				if(treearray[i] == ini[v]){
					printf("%d %d\n",i,i);
					flag = 1;
				}
				else if(i + 1 <= r && func(treearray[i],treearray[i+1]).second == v ){
					printf("%d %d\n",i,i+1);
					flag = 1;
				}
			}
			if(!flag) printf("-1 -1\n");
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&q);
                            ^
treearray.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
                       ^
treearray.cpp:49:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&treearray[i]);
                            ^
treearray.cpp:54:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&operacao);
                        ^
treearray.cpp:57:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&idx,&v);
                          ^
treearray.cpp:62:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d",&l,&r,&v);
                              ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4984 KB	n=5
2	Correct	5 ms	5088 KB	n=100
3	Correct	6 ms	5288 KB	n=100
4	Correct	6 ms	5288 KB	n=100
5	Correct	5 ms	5288 KB	n=100
6	Correct	5 ms	5288 KB	n=100
7	Correct	5 ms	5288 KB	n=100
8	Correct	5 ms	5288 KB	n=100
9	Correct	5 ms	5288 KB	n=100
10	Correct	6 ms	5320 KB	n=100
11	Correct	5 ms	5320 KB	n=100
12	Correct	5 ms	5320 KB	n=100
13	Correct	5 ms	5320 KB	n=100
14	Correct	5 ms	5320 KB	n=100
15	Correct	5 ms	5320 KB	n=100
16	Correct	5 ms	5320 KB	n=100
17	Correct	6 ms	5320 KB	n=100
18	Correct	5 ms	5320 KB	n=100
19	Correct	5 ms	5320 KB	n=100
20	Correct	5 ms	5320 KB	n=100
21	Correct	5 ms	5320 KB	n=100
22	Correct	5 ms	5320 KB	n=100
23	Correct	6 ms	5320 KB	n=100
24	Correct	5 ms	5320 KB	n=100
25	Correct	6 ms	5320 KB	n=100
26	Correct	5 ms	5320 KB	n=12
27	Correct	5 ms	5320 KB	n=100
28	Correct	5 ms	5340 KB	n=500
29	Correct	11 ms	5340 KB	n=500
30	Correct	12 ms	5340 KB	n=500
31	Correct	11 ms	5340 KB	n=500
32	Correct	6 ms	5340 KB	n=500
33	Correct	10 ms	5340 KB	n=500
34	Correct	5 ms	5340 KB	n=500
35	Correct	10 ms	5340 KB	n=500
36	Correct	39 ms	5364 KB	n=500
37	Correct	37 ms	5364 KB	n=500
38	Correct	37 ms	5364 KB	n=500
39	Correct	21 ms	5364 KB	n=500
40	Correct	24 ms	5364 KB	n=500
41	Correct	21 ms	5364 KB	n=500
42	Correct	23 ms	5364 KB	n=500
43	Correct	23 ms	5364 KB	n=500
44	Correct	27 ms	5364 KB	n=500
45	Correct	5 ms	5364 KB	n=500
46	Correct	11 ms	5364 KB	n=500
47	Correct	9 ms	5364 KB	n=500
48	Correct	6 ms	5364 KB	n=500
49	Correct	9 ms	5364 KB	n=500
50	Correct	14 ms	5416 KB	n=500
51	Correct	13 ms	5416 KB	n=500
52	Correct	16 ms	5416 KB	n=500
53	Correct	19 ms	5416 KB	n=500
54	Correct	26 ms	5416 KB	n=500
55	Correct	6 ms	5416 KB	n=278
56	Correct	31 ms	5416 KB	n=500
57	Correct	30 ms	5416 KB	n=500
58	Correct	31 ms	5416 KB	n=500
59	Correct	8 ms	5468 KB	n=2000
60	Correct	115 ms	5724 KB	n=2000
61	Correct	119 ms	5724 KB	n=2000
62	Correct	90 ms	5724 KB	n=2000
63	Correct	9 ms	5724 KB	n=2000
64	Correct	102 ms	5724 KB	n=2000
65	Correct	8 ms	5724 KB	n=2000
66	Correct	131 ms	5724 KB	n=2000
67	Correct	13 ms	5724 KB	n=2000
68	Correct	109 ms	5724 KB	n=2000
69	Correct	737 ms	5788 KB	n=2000
70	Correct	775 ms	5796 KB	n=2000
71	Correct	753 ms	5796 KB	n=2000
72	Correct	383 ms	5796 KB	n=2000
73	Correct	367 ms	5796 KB	n=2000
74	Correct	8 ms	5796 KB	n=1844
75	Correct	405 ms	5796 KB	n=2000
76	Correct	408 ms	5796 KB	n=2000
77	Correct	396 ms	5796 KB	n=2000
78	Correct	391 ms	5796 KB	n=2000
79	Correct	9 ms	5796 KB	n=2000
80	Correct	109 ms	5796 KB	n=2000
81	Correct	92 ms	5796 KB	n=2000
82	Correct	7 ms	5796 KB	n=2000
83	Correct	120 ms	5796 KB	n=2000
84	Correct	205 ms	5796 KB	n=2000
85	Correct	193 ms	5796 KB	n=2000
86	Correct	213 ms	5796 KB	n=2000
87	Correct	212 ms	5796 KB	n=2000
88	Correct	621 ms	5916 KB	n=2000
89	Correct	626 ms	5916 KB	n=2000
90	Correct	312 ms	5916 KB	n=2000
91	Correct	573 ms	5916 KB	n=2000

Subtask #4
0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4984 KB	n=5
2	Correct	5 ms	5088 KB	n=100
3	Correct	6 ms	5288 KB	n=100
4	Correct	6 ms	5288 KB	n=100
5	Correct	5 ms	5288 KB	n=100
6	Correct	5 ms	5288 KB	n=100
7	Correct	5 ms	5288 KB	n=100
8	Correct	5 ms	5288 KB	n=100
9	Correct	5 ms	5288 KB	n=100
10	Correct	6 ms	5320 KB	n=100
11	Correct	5 ms	5320 KB	n=100
12	Correct	5 ms	5320 KB	n=100
13	Correct	5 ms	5320 KB	n=100
14	Correct	5 ms	5320 KB	n=100
15	Correct	5 ms	5320 KB	n=100
16	Correct	5 ms	5320 KB	n=100
17	Correct	6 ms	5320 KB	n=100
18	Correct	5 ms	5320 KB	n=100
19	Correct	5 ms	5320 KB	n=100
20	Correct	5 ms	5320 KB	n=100
21	Correct	5 ms	5320 KB	n=100
22	Correct	5 ms	5320 KB	n=100
23	Correct	6 ms	5320 KB	n=100
24	Correct	5 ms	5320 KB	n=100
25	Correct	6 ms	5320 KB	n=100
26	Correct	5 ms	5320 KB	n=12
27	Correct	5 ms	5320 KB	n=100
28	Correct	5 ms	5340 KB	n=500
29	Correct	11 ms	5340 KB	n=500
30	Correct	12 ms	5340 KB	n=500
31	Correct	11 ms	5340 KB	n=500
32	Correct	6 ms	5340 KB	n=500
33	Correct	10 ms	5340 KB	n=500
34	Correct	5 ms	5340 KB	n=500
35	Correct	10 ms	5340 KB	n=500
36	Correct	39 ms	5364 KB	n=500
37	Correct	37 ms	5364 KB	n=500
38	Correct	37 ms	5364 KB	n=500
39	Correct	21 ms	5364 KB	n=500
40	Correct	24 ms	5364 KB	n=500
41	Correct	21 ms	5364 KB	n=500
42	Correct	23 ms	5364 KB	n=500
43	Correct	23 ms	5364 KB	n=500
44	Correct	27 ms	5364 KB	n=500
45	Correct	5 ms	5364 KB	n=500
46	Correct	11 ms	5364 KB	n=500
47	Correct	9 ms	5364 KB	n=500
48	Correct	6 ms	5364 KB	n=500
49	Correct	9 ms	5364 KB	n=500
50	Correct	14 ms	5416 KB	n=500
51	Correct	13 ms	5416 KB	n=500
52	Correct	16 ms	5416 KB	n=500
53	Correct	19 ms	5416 KB	n=500
54	Correct	26 ms	5416 KB	n=500
55	Correct	6 ms	5416 KB	n=278
56	Correct	31 ms	5416 KB	n=500
57	Correct	30 ms	5416 KB	n=500
58	Correct	31 ms	5416 KB	n=500
59	Correct	8 ms	5468 KB	n=2000
60	Correct	115 ms	5724 KB	n=2000
61	Correct	119 ms	5724 KB	n=2000
62	Correct	90 ms	5724 KB	n=2000
63	Correct	9 ms	5724 KB	n=2000
64	Correct	102 ms	5724 KB	n=2000
65	Correct	8 ms	5724 KB	n=2000
66	Correct	131 ms	5724 KB	n=2000
67	Correct	13 ms	5724 KB	n=2000
68	Correct	109 ms	5724 KB	n=2000
69	Correct	737 ms	5788 KB	n=2000
70	Correct	775 ms	5796 KB	n=2000
71	Correct	753 ms	5796 KB	n=2000
72	Correct	383 ms	5796 KB	n=2000
73	Correct	367 ms	5796 KB	n=2000
74	Correct	8 ms	5796 KB	n=1844
75	Correct	405 ms	5796 KB	n=2000
76	Correct	408 ms	5796 KB	n=2000
77	Correct	396 ms	5796 KB	n=2000
78	Correct	391 ms	5796 KB	n=2000
79	Correct	9 ms	5796 KB	n=2000
80	Correct	109 ms	5796 KB	n=2000
81	Correct	92 ms	5796 KB	n=2000
82	Correct	7 ms	5796 KB	n=2000
83	Correct	120 ms	5796 KB	n=2000
84	Correct	205 ms	5796 KB	n=2000
85	Correct	193 ms	5796 KB	n=2000
86	Correct	213 ms	5796 KB	n=2000
87	Correct	212 ms	5796 KB	n=2000
88	Correct	621 ms	5916 KB	n=2000
89	Correct	626 ms	5916 KB	n=2000
90	Correct	312 ms	5916 KB	n=2000
91	Correct	573 ms	5916 KB	n=2000
92	Correct	2318 ms	26656 KB	n=200000
93	Execution timed out	4096 ms	34972 KB	Time limit exceeded
94	Halted	0 ms	0 KB	-

답안 #41687

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