답안 #41679 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41679	2018-02-20T12:23:18 Z	IvanC	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4000 ms	34248 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){
	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);
			deque<ii> minQ,maxQ;
			int i = l;
			for(int j = l;j<=r && !flag;j++){
				ii novo = ii(treearray[j],j);
				while(!minQ.empty() && minQ.back() >= novo) minQ.pop_back();
				while(!maxQ.empty() && maxQ.back() <= novo) maxQ.pop_back();
				minQ.push_back(novo);
				maxQ.push_back(novo);
				while(!minQ.empty() && !maxQ.empty() && func(minQ.front().first,maxQ.front().first).first < vetorzao[ini[v]].first){
					if(minQ.front().second == i) minQ.pop_front();
					if(maxQ.front().second == i) maxQ.pop_front();
					i++;
				}
				if(!minQ.empty() && !maxQ.empty() && func(minQ.front().first,maxQ.front().first).second == v ){
					printf("%d %d\n",i,j);
					flag = 1;
				}
			}
			if(!flag) printf("-1 -1\n");
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:38: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:41: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:48:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&treearray[i]);
                            ^
treearray.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&operacao);
                        ^
treearray.cpp:56: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:61: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	5056 KB	n=5
2	Correct	5 ms	5092 KB	n=100
3	Correct	6 ms	5288 KB	n=100
4	Correct	5 ms	5288 KB	n=100
5	Correct	6 ms	5288 KB	n=100
6	Correct	7 ms	5288 KB	n=100
7	Correct	7 ms	5304 KB	n=100
8	Correct	6 ms	5304 KB	n=100
9	Correct	6 ms	5304 KB	n=100
10	Correct	6 ms	5304 KB	n=100
11	Correct	6 ms	5304 KB	n=100
12	Correct	5 ms	5304 KB	n=100
13	Correct	6 ms	5304 KB	n=100
14	Correct	5 ms	5304 KB	n=100
15	Correct	6 ms	5304 KB	n=100
16	Correct	6 ms	5304 KB	n=100
17	Correct	6 ms	5304 KB	n=100
18	Correct	6 ms	5304 KB	n=100
19	Correct	5 ms	5304 KB	n=100
20	Correct	6 ms	5304 KB	n=100
21	Correct	7 ms	5304 KB	n=100
22	Correct	5 ms	5304 KB	n=100
23	Correct	6 ms	5304 KB	n=100
24	Correct	7 ms	5304 KB	n=100
25	Correct	6 ms	5304 KB	n=100
26	Correct	6 ms	5304 KB	n=12
27	Correct	7 ms	5304 KB	n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5056 KB	n=5
2	Correct	5 ms	5092 KB	n=100
3	Correct	6 ms	5288 KB	n=100
4	Correct	5 ms	5288 KB	n=100
5	Correct	6 ms	5288 KB	n=100
6	Correct	7 ms	5288 KB	n=100
7	Correct	7 ms	5304 KB	n=100
8	Correct	6 ms	5304 KB	n=100
9	Correct	6 ms	5304 KB	n=100
10	Correct	6 ms	5304 KB	n=100
11	Correct	6 ms	5304 KB	n=100
12	Correct	5 ms	5304 KB	n=100
13	Correct	6 ms	5304 KB	n=100
14	Correct	5 ms	5304 KB	n=100
15	Correct	6 ms	5304 KB	n=100
16	Correct	6 ms	5304 KB	n=100
17	Correct	6 ms	5304 KB	n=100
18	Correct	6 ms	5304 KB	n=100
19	Correct	5 ms	5304 KB	n=100
20	Correct	6 ms	5304 KB	n=100
21	Correct	7 ms	5304 KB	n=100
22	Correct	5 ms	5304 KB	n=100
23	Correct	6 ms	5304 KB	n=100
24	Correct	7 ms	5304 KB	n=100
25	Correct	6 ms	5304 KB	n=100
26	Correct	6 ms	5304 KB	n=12
27	Correct	7 ms	5304 KB	n=100
28	Correct	8 ms	5340 KB	n=500
29	Correct	16 ms	5340 KB	n=500
30	Correct	16 ms	5340 KB	n=500
31	Correct	15 ms	5380 KB	n=500
32	Correct	6 ms	5380 KB	n=500
33	Correct	13 ms	5380 KB	n=500
34	Correct	6 ms	5380 KB	n=500
35	Correct	16 ms	5380 KB	n=500
36	Correct	81 ms	5380 KB	n=500
37	Correct	74 ms	5380 KB	n=500
38	Correct	74 ms	5468 KB	n=500
39	Correct	42 ms	5468 KB	n=500
40	Correct	41 ms	5468 KB	n=500
41	Correct	39 ms	5468 KB	n=500
42	Correct	41 ms	5468 KB	n=500
43	Correct	45 ms	5468 KB	n=500
44	Correct	40 ms	5468 KB	n=500
45	Correct	6 ms	5468 KB	n=500
46	Correct	16 ms	5468 KB	n=500
47	Correct	13 ms	5468 KB	n=500
48	Correct	6 ms	5468 KB	n=500
49	Correct	14 ms	5468 KB	n=500
50	Correct	25 ms	5468 KB	n=500
51	Correct	19 ms	5468 KB	n=500
52	Correct	20 ms	5468 KB	n=500
53	Correct	19 ms	5468 KB	n=500
54	Correct	25 ms	5472 KB	n=500
55	Correct	7 ms	5472 KB	n=278
56	Correct	42 ms	5472 KB	n=500
57	Correct	42 ms	5472 KB	n=500
58	Correct	42 ms	5472 KB	n=500
59	Correct	10 ms	5472 KB	n=2000
60	Correct	181 ms	5612 KB	n=2000
61	Correct	186 ms	5612 KB	n=2000
62	Correct	119 ms	5688 KB	n=2000
63	Correct	12 ms	5688 KB	n=2000
64	Correct	165 ms	5688 KB	n=2000
65	Correct	9 ms	5688 KB	n=2000
66	Correct	204 ms	5688 KB	n=2000
67	Correct	20 ms	5688 KB	n=2000
68	Correct	169 ms	5688 KB	n=2000
69	Correct	1406 ms	5932 KB	n=2000
70	Correct	1457 ms	5932 KB	n=2000
71	Correct	1385 ms	5968 KB	n=2000
72	Correct	715 ms	5968 KB	n=2000
73	Correct	697 ms	5968 KB	n=2000
74	Correct	8 ms	5968 KB	n=1844
75	Correct	706 ms	6048 KB	n=2000
76	Correct	753 ms	6048 KB	n=2000
77	Correct	770 ms	6048 KB	n=2000
78	Correct	766 ms	6048 KB	n=2000
79	Correct	8 ms	6048 KB	n=2000
80	Correct	170 ms	6180 KB	n=2000
81	Correct	148 ms	6236 KB	n=2000
82	Correct	9 ms	6236 KB	n=2000
83	Correct	158 ms	6468 KB	n=2000
84	Correct	347 ms	6468 KB	n=2000
85	Correct	252 ms	6576 KB	n=2000
86	Correct	252 ms	6576 KB	n=2000
87	Correct	379 ms	6576 KB	n=2000
88	Correct	789 ms	6816 KB	n=2000
89	Correct	627 ms	6816 KB	n=2000
90	Correct	450 ms	6852 KB	n=2000
91	Correct	1000 ms	6904 KB	n=2000

Subtask #4
0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	5056 KB	n=5
2	Correct	5 ms	5092 KB	n=100
3	Correct	6 ms	5288 KB	n=100
4	Correct	5 ms	5288 KB	n=100
5	Correct	6 ms	5288 KB	n=100
6	Correct	7 ms	5288 KB	n=100
7	Correct	7 ms	5304 KB	n=100
8	Correct	6 ms	5304 KB	n=100
9	Correct	6 ms	5304 KB	n=100
10	Correct	6 ms	5304 KB	n=100
11	Correct	6 ms	5304 KB	n=100
12	Correct	5 ms	5304 KB	n=100
13	Correct	6 ms	5304 KB	n=100
14	Correct	5 ms	5304 KB	n=100
15	Correct	6 ms	5304 KB	n=100
16	Correct	6 ms	5304 KB	n=100
17	Correct	6 ms	5304 KB	n=100
18	Correct	6 ms	5304 KB	n=100
19	Correct	5 ms	5304 KB	n=100
20	Correct	6 ms	5304 KB	n=100
21	Correct	7 ms	5304 KB	n=100
22	Correct	5 ms	5304 KB	n=100
23	Correct	6 ms	5304 KB	n=100
24	Correct	7 ms	5304 KB	n=100
25	Correct	6 ms	5304 KB	n=100
26	Correct	6 ms	5304 KB	n=12
27	Correct	7 ms	5304 KB	n=100
28	Correct	8 ms	5340 KB	n=500
29	Correct	16 ms	5340 KB	n=500
30	Correct	16 ms	5340 KB	n=500
31	Correct	15 ms	5380 KB	n=500
32	Correct	6 ms	5380 KB	n=500
33	Correct	13 ms	5380 KB	n=500
34	Correct	6 ms	5380 KB	n=500
35	Correct	16 ms	5380 KB	n=500
36	Correct	81 ms	5380 KB	n=500
37	Correct	74 ms	5380 KB	n=500
38	Correct	74 ms	5468 KB	n=500
39	Correct	42 ms	5468 KB	n=500
40	Correct	41 ms	5468 KB	n=500
41	Correct	39 ms	5468 KB	n=500
42	Correct	41 ms	5468 KB	n=500
43	Correct	45 ms	5468 KB	n=500
44	Correct	40 ms	5468 KB	n=500
45	Correct	6 ms	5468 KB	n=500
46	Correct	16 ms	5468 KB	n=500
47	Correct	13 ms	5468 KB	n=500
48	Correct	6 ms	5468 KB	n=500
49	Correct	14 ms	5468 KB	n=500
50	Correct	25 ms	5468 KB	n=500
51	Correct	19 ms	5468 KB	n=500
52	Correct	20 ms	5468 KB	n=500
53	Correct	19 ms	5468 KB	n=500
54	Correct	25 ms	5472 KB	n=500
55	Correct	7 ms	5472 KB	n=278
56	Correct	42 ms	5472 KB	n=500
57	Correct	42 ms	5472 KB	n=500
58	Correct	42 ms	5472 KB	n=500
59	Correct	10 ms	5472 KB	n=2000
60	Correct	181 ms	5612 KB	n=2000
61	Correct	186 ms	5612 KB	n=2000
62	Correct	119 ms	5688 KB	n=2000
63	Correct	12 ms	5688 KB	n=2000
64	Correct	165 ms	5688 KB	n=2000
65	Correct	9 ms	5688 KB	n=2000
66	Correct	204 ms	5688 KB	n=2000
67	Correct	20 ms	5688 KB	n=2000
68	Correct	169 ms	5688 KB	n=2000
69	Correct	1406 ms	5932 KB	n=2000
70	Correct	1457 ms	5932 KB	n=2000
71	Correct	1385 ms	5968 KB	n=2000
72	Correct	715 ms	5968 KB	n=2000
73	Correct	697 ms	5968 KB	n=2000
74	Correct	8 ms	5968 KB	n=1844
75	Correct	706 ms	6048 KB	n=2000
76	Correct	753 ms	6048 KB	n=2000
77	Correct	770 ms	6048 KB	n=2000
78	Correct	766 ms	6048 KB	n=2000
79	Correct	8 ms	6048 KB	n=2000
80	Correct	170 ms	6180 KB	n=2000
81	Correct	148 ms	6236 KB	n=2000
82	Correct	9 ms	6236 KB	n=2000
83	Correct	158 ms	6468 KB	n=2000
84	Correct	347 ms	6468 KB	n=2000
85	Correct	252 ms	6576 KB	n=2000
86	Correct	252 ms	6576 KB	n=2000
87	Correct	379 ms	6576 KB	n=2000
88	Correct	789 ms	6816 KB	n=2000
89	Correct	627 ms	6816 KB	n=2000
90	Correct	450 ms	6852 KB	n=2000
91	Correct	1000 ms	6904 KB	n=2000
92	Execution timed out	4077 ms	34248 KB	Time limit exceeded
93	Halted	0 ms	0 KB	-

답안 #41679

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