답안 #41675 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41675	2018-02-20T11:49:15 Z	IvanC	Birthday gift (IZhO18_treearray)	C++14	30 / 100	4000 ms	6908 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,leftmost[MAXN],rightmost[MAXN],treearray[MAXN],n,m,q;
ii vetorzao[2*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);
	}
}
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);
	for(int v = 1;v<=n;v++){
		int ptr = ini[v];
		while(ptr + 1 <= dfsNum && ((vetorzao[ptr+1].first > vetorzao[ini[v]].first) || (vetorzao[ptr+1] == vetorzao[ini[v]]))){
			ptr++;
		}
		rightmost[v] = ptr;
		ptr = ini[v];
		while(ptr - 1 >= 1 && ((vetorzao[ptr-1].first > vetorzao[ini[v]].first) || (vetorzao[ptr-1] == vetorzao[ini[v]]))){
			ptr--;
		}
		leftmost[v] = ptr;
	}
	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++){
				int minimo = treearray[i],maximo = treearray[i],lo = treearray[i],hi = treearray[i];
				ii ancestral = ii(vetorzao[minimo]);
				for(int j = i;j<=r && !flag;j++){
					minimo = min(minimo,treearray[j]);
					maximo = max(maximo,treearray[j]);
					while(hi +1 <= maximo){
						ancestral = min(ancestral,vetorzao[hi+1]);
						hi++;
					}
					while(lo - 1 >= minimo){
						ancestral = min(ancestral,vetorzao[lo-1]);
						lo--;
					}
					if(ancestral.second == v){
						printf("%d %d\n",i,j);
						flag = 1;
					}
					else if(ancestral.first < vetorzao[ini[v]].first){
						break;
					}
				}
			}
			if(!flag) printf("-1 -1\n");
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:18: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:21: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:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&treearray[i]);
                            ^
treearray.cpp:44:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&operacao);
                        ^
treearray.cpp:47: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:52: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	5 ms	5088 KB	n=100
4	Correct	6 ms	5088 KB	n=100
5	Correct	6 ms	5132 KB	n=100
6	Correct	7 ms	5240 KB	n=100
7	Correct	7 ms	5260 KB	n=100
8	Correct	6 ms	5260 KB	n=100
9	Correct	6 ms	5260 KB	n=100
10	Correct	5 ms	5260 KB	n=100
11	Correct	6 ms	5260 KB	n=100
12	Correct	5 ms	5368 KB	n=100
13	Correct	6 ms	5368 KB	n=100
14	Correct	5 ms	5368 KB	n=100
15	Correct	6 ms	5368 KB	n=100
16	Correct	5 ms	5368 KB	n=100
17	Correct	6 ms	5368 KB	n=100
18	Correct	6 ms	5368 KB	n=100
19	Correct	5 ms	5372 KB	n=100
20	Correct	5 ms	5376 KB	n=100
21	Correct	6 ms	5508 KB	n=100
22	Correct	5 ms	5508 KB	n=100
23	Correct	6 ms	5508 KB	n=100
24	Correct	6 ms	5508 KB	n=100
25	Correct	5 ms	5508 KB	n=100
26	Correct	6 ms	5508 KB	n=12
27	Correct	5 ms	5508 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	5 ms	5088 KB	n=100
4	Correct	6 ms	5088 KB	n=100
5	Correct	6 ms	5132 KB	n=100
6	Correct	7 ms	5240 KB	n=100
7	Correct	7 ms	5260 KB	n=100
8	Correct	6 ms	5260 KB	n=100
9	Correct	6 ms	5260 KB	n=100
10	Correct	5 ms	5260 KB	n=100
11	Correct	6 ms	5260 KB	n=100
12	Correct	5 ms	5368 KB	n=100
13	Correct	6 ms	5368 KB	n=100
14	Correct	5 ms	5368 KB	n=100
15	Correct	6 ms	5368 KB	n=100
16	Correct	5 ms	5368 KB	n=100
17	Correct	6 ms	5368 KB	n=100
18	Correct	6 ms	5368 KB	n=100
19	Correct	5 ms	5372 KB	n=100
20	Correct	5 ms	5376 KB	n=100
21	Correct	6 ms	5508 KB	n=100
22	Correct	5 ms	5508 KB	n=100
23	Correct	6 ms	5508 KB	n=100
24	Correct	6 ms	5508 KB	n=100
25	Correct	5 ms	5508 KB	n=100
26	Correct	6 ms	5508 KB	n=12
27	Correct	5 ms	5508 KB	n=100
28	Correct	6 ms	5536 KB	n=500
29	Correct	14 ms	5548 KB	n=500
30	Correct	21 ms	5612 KB	n=500
31	Correct	18 ms	5612 KB	n=500
32	Correct	7 ms	5612 KB	n=500
33	Correct	20 ms	5624 KB	n=500
34	Correct	6 ms	5640 KB	n=500
35	Correct	13 ms	5696 KB	n=500
36	Correct	102 ms	5700 KB	n=500
37	Correct	101 ms	5856 KB	n=500
38	Correct	111 ms	5856 KB	n=500
39	Correct	55 ms	5856 KB	n=500
40	Correct	51 ms	5856 KB	n=500
41	Correct	56 ms	5856 KB	n=500
42	Correct	57 ms	5856 KB	n=500
43	Correct	55 ms	5856 KB	n=500
44	Correct	60 ms	5856 KB	n=500
45	Correct	6 ms	5856 KB	n=500
46	Correct	14 ms	5856 KB	n=500
47	Correct	14 ms	5864 KB	n=500
48	Correct	6 ms	5884 KB	n=500
49	Correct	13 ms	5892 KB	n=500
50	Correct	50 ms	6036 KB	n=500
51	Correct	22 ms	6036 KB	n=500
52	Correct	17 ms	6036 KB	n=500
53	Correct	24 ms	6036 KB	n=500
54	Correct	27 ms	6036 KB	n=500
55	Correct	6 ms	6036 KB	n=278
56	Correct	141 ms	6036 KB	n=500
57	Correct	149 ms	6132 KB	n=500
58	Correct	37 ms	6132 KB	n=500

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4984 KB	n=5
2	Correct	5 ms	5088 KB	n=100
3	Correct	5 ms	5088 KB	n=100
4	Correct	6 ms	5088 KB	n=100
5	Correct	6 ms	5132 KB	n=100
6	Correct	7 ms	5240 KB	n=100
7	Correct	7 ms	5260 KB	n=100
8	Correct	6 ms	5260 KB	n=100
9	Correct	6 ms	5260 KB	n=100
10	Correct	5 ms	5260 KB	n=100
11	Correct	6 ms	5260 KB	n=100
12	Correct	5 ms	5368 KB	n=100
13	Correct	6 ms	5368 KB	n=100
14	Correct	5 ms	5368 KB	n=100
15	Correct	6 ms	5368 KB	n=100
16	Correct	5 ms	5368 KB	n=100
17	Correct	6 ms	5368 KB	n=100
18	Correct	6 ms	5368 KB	n=100
19	Correct	5 ms	5372 KB	n=100
20	Correct	5 ms	5376 KB	n=100
21	Correct	6 ms	5508 KB	n=100
22	Correct	5 ms	5508 KB	n=100
23	Correct	6 ms	5508 KB	n=100
24	Correct	6 ms	5508 KB	n=100
25	Correct	5 ms	5508 KB	n=100
26	Correct	6 ms	5508 KB	n=12
27	Correct	5 ms	5508 KB	n=100
28	Correct	6 ms	5536 KB	n=500
29	Correct	14 ms	5548 KB	n=500
30	Correct	21 ms	5612 KB	n=500
31	Correct	18 ms	5612 KB	n=500
32	Correct	7 ms	5612 KB	n=500
33	Correct	20 ms	5624 KB	n=500
34	Correct	6 ms	5640 KB	n=500
35	Correct	13 ms	5696 KB	n=500
36	Correct	102 ms	5700 KB	n=500
37	Correct	101 ms	5856 KB	n=500
38	Correct	111 ms	5856 KB	n=500
39	Correct	55 ms	5856 KB	n=500
40	Correct	51 ms	5856 KB	n=500
41	Correct	56 ms	5856 KB	n=500
42	Correct	57 ms	5856 KB	n=500
43	Correct	55 ms	5856 KB	n=500
44	Correct	60 ms	5856 KB	n=500
45	Correct	6 ms	5856 KB	n=500
46	Correct	14 ms	5856 KB	n=500
47	Correct	14 ms	5864 KB	n=500
48	Correct	6 ms	5884 KB	n=500
49	Correct	13 ms	5892 KB	n=500
50	Correct	50 ms	6036 KB	n=500
51	Correct	22 ms	6036 KB	n=500
52	Correct	17 ms	6036 KB	n=500
53	Correct	24 ms	6036 KB	n=500
54	Correct	27 ms	6036 KB	n=500
55	Correct	6 ms	6036 KB	n=278
56	Correct	141 ms	6036 KB	n=500
57	Correct	149 ms	6132 KB	n=500
58	Correct	37 ms	6132 KB	n=500
59	Correct	19 ms	6160 KB	n=2000
60	Correct	421 ms	6364 KB	n=2000
61	Correct	824 ms	6396 KB	n=2000
62	Correct	657 ms	6452 KB	n=2000
63	Correct	31 ms	6452 KB	n=2000
64	Correct	861 ms	6560 KB	n=2000
65	Correct	16 ms	6560 KB	n=2000
66	Correct	787 ms	6796 KB	n=2000
67	Correct	36 ms	6796 KB	n=2000
68	Correct	815 ms	6908 KB	n=2000
69	Execution timed out	4048 ms	6908 KB	Time limit exceeded
70	Halted	0 ms	0 KB	-

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	5 ms	5088 KB	n=100
4	Correct	6 ms	5088 KB	n=100
5	Correct	6 ms	5132 KB	n=100
6	Correct	7 ms	5240 KB	n=100
7	Correct	7 ms	5260 KB	n=100
8	Correct	6 ms	5260 KB	n=100
9	Correct	6 ms	5260 KB	n=100
10	Correct	5 ms	5260 KB	n=100
11	Correct	6 ms	5260 KB	n=100
12	Correct	5 ms	5368 KB	n=100
13	Correct	6 ms	5368 KB	n=100
14	Correct	5 ms	5368 KB	n=100
15	Correct	6 ms	5368 KB	n=100
16	Correct	5 ms	5368 KB	n=100
17	Correct	6 ms	5368 KB	n=100
18	Correct	6 ms	5368 KB	n=100
19	Correct	5 ms	5372 KB	n=100
20	Correct	5 ms	5376 KB	n=100
21	Correct	6 ms	5508 KB	n=100
22	Correct	5 ms	5508 KB	n=100
23	Correct	6 ms	5508 KB	n=100
24	Correct	6 ms	5508 KB	n=100
25	Correct	5 ms	5508 KB	n=100
26	Correct	6 ms	5508 KB	n=12
27	Correct	5 ms	5508 KB	n=100
28	Correct	6 ms	5536 KB	n=500
29	Correct	14 ms	5548 KB	n=500
30	Correct	21 ms	5612 KB	n=500
31	Correct	18 ms	5612 KB	n=500
32	Correct	7 ms	5612 KB	n=500
33	Correct	20 ms	5624 KB	n=500
34	Correct	6 ms	5640 KB	n=500
35	Correct	13 ms	5696 KB	n=500
36	Correct	102 ms	5700 KB	n=500
37	Correct	101 ms	5856 KB	n=500
38	Correct	111 ms	5856 KB	n=500
39	Correct	55 ms	5856 KB	n=500
40	Correct	51 ms	5856 KB	n=500
41	Correct	56 ms	5856 KB	n=500
42	Correct	57 ms	5856 KB	n=500
43	Correct	55 ms	5856 KB	n=500
44	Correct	60 ms	5856 KB	n=500
45	Correct	6 ms	5856 KB	n=500
46	Correct	14 ms	5856 KB	n=500
47	Correct	14 ms	5864 KB	n=500
48	Correct	6 ms	5884 KB	n=500
49	Correct	13 ms	5892 KB	n=500
50	Correct	50 ms	6036 KB	n=500
51	Correct	22 ms	6036 KB	n=500
52	Correct	17 ms	6036 KB	n=500
53	Correct	24 ms	6036 KB	n=500
54	Correct	27 ms	6036 KB	n=500
55	Correct	6 ms	6036 KB	n=278
56	Correct	141 ms	6036 KB	n=500
57	Correct	149 ms	6132 KB	n=500
58	Correct	37 ms	6132 KB	n=500
59	Correct	19 ms	6160 KB	n=2000
60	Correct	421 ms	6364 KB	n=2000
61	Correct	824 ms	6396 KB	n=2000
62	Correct	657 ms	6452 KB	n=2000
63	Correct	31 ms	6452 KB	n=2000
64	Correct	861 ms	6560 KB	n=2000
65	Correct	16 ms	6560 KB	n=2000
66	Correct	787 ms	6796 KB	n=2000
67	Correct	36 ms	6796 KB	n=2000
68	Correct	815 ms	6908 KB	n=2000
69	Execution timed out	4048 ms	6908 KB	Time limit exceeded
70	Halted	0 ms	0 KB	-

답안 #41675

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 0 / 26.0

Subtask #4 0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
0 / 26.0

Subtask #4
0 / 44.0