답안 #85406 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
85406	2018-11-19T19:23:52 Z	farukkastamonuda	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1583 ms	176468 KB

treearray

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 200005
#define mid (start+end)/2
using namespace std;
int n,m,q,x,y,dep[li],baba[24][li],A[li],deg;
vector<int> v[li];
set<int> s[li],t[li];
void dfs(int node,int ata,int d){
	baba[0][node]=ata;
	dep[node]=d;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata) continue;
		dfs(go,node,d+1);
	}
}
void b_lca(){
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n;j++){
			baba[i][j]=baba[i-1][baba[i-1][j]];
		}
	}
}
int f_lca(int x,int y){
	if(x==0 || y==0) return x+y;
	if(dep[x]<dep[y]) swap(x,y);
	int dx=dep[x];
	int dy=dep[y];
	for(int i=20;i>=0;i--){
		if(dx-(1<<i)>=dy){
			dx-=(1<<i);
			x=baba[i][x];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(baba[i][x]!=baba[i][y]){
			x=baba[i][x];
			y=baba[i][y];
		}
	}
	return baba[0][x];
}
int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
		s[i].insert(inf);
		t[i].insert(inf);
	}
	t[n].insert(inf);
	s[n].insert(inf);
	dfs(1,0,0);
	b_lca();
	for(int i=1;i<=m;i++){
		scanf("%d",&A[i]);
		t[A[i]].insert(i);
	}
	for(int i=1;i<m;i++){
		s[f_lca(A[i],A[i+1])].insert(i);
	}
	for(int i=1;i<=q;i++){
		int tt,ll;
		scanf("%d %d",&tt,&ll);
		if(tt==2){
			int rr,vv;
			scanf("%d %d",&rr,&vv);
			int tut1=*t[vv].lower_bound(ll);
			int tut2=*s[vv].lower_bound(ll);
			if(tut1<=rr){
				printf("%d %d\n",tut1,tut1);
			}
			else if(tut2<=rr-1){
				printf("%d %d\n",tut2,tut2+1);
			}
			else{
				printf("-1 -1\n");
			}
		}
		else{
			int vv;
			scanf("%d",&vv);
			t[A[ll]].erase(ll);
			t[vv].insert(ll);
			if(ll>1){
				int x=f_lca(A[ll-1],A[ll]);
				s[x].erase(ll-1);
				x=f_lca(vv,A[ll-1]);
				s[x].insert(ll-1);
			}
			if(ll<m){
				int x=f_lca(A[ll],A[ll+1]);
				s[x].erase(ll);
				x=f_lca(vv,A[ll+1]);
				s[x].insert(ll);
			}
			A[ll]=vv;
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:52:7: 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:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
treearray.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~
treearray.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&tt,&ll);
   ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&rr,&vv);
    ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&vv);
    ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	n=5
2	Correct	21 ms	24060 KB	n=100
3	Correct	21 ms	24140 KB	n=100
4	Correct	20 ms	24140 KB	n=100
5	Correct	22 ms	24172 KB	n=100
6	Correct	22 ms	24172 KB	n=100
7	Correct	21 ms	24172 KB	n=100
8	Correct	21 ms	24228 KB	n=100
9	Correct	22 ms	24228 KB	n=100
10	Correct	23 ms	24228 KB	n=100
11	Correct	23 ms	24228 KB	n=100
12	Correct	21 ms	24228 KB	n=100
13	Correct	22 ms	24228 KB	n=100
14	Correct	21 ms	24228 KB	n=100
15	Correct	22 ms	24228 KB	n=100
16	Correct	22 ms	24240 KB	n=100
17	Correct	22 ms	24240 KB	n=100
18	Correct	21 ms	24244 KB	n=100
19	Correct	22 ms	24244 KB	n=100
20	Correct	21 ms	24244 KB	n=100
21	Correct	22 ms	24244 KB	n=100
22	Correct	23 ms	24244 KB	n=100
23	Correct	21 ms	24244 KB	n=100
24	Correct	21 ms	24244 KB	n=100
25	Correct	22 ms	24276 KB	n=100
26	Correct	21 ms	24276 KB	n=12
27	Correct	21 ms	24276 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	n=5
2	Correct	21 ms	24060 KB	n=100
3	Correct	21 ms	24140 KB	n=100
4	Correct	20 ms	24140 KB	n=100
5	Correct	22 ms	24172 KB	n=100
6	Correct	22 ms	24172 KB	n=100
7	Correct	21 ms	24172 KB	n=100
8	Correct	21 ms	24228 KB	n=100
9	Correct	22 ms	24228 KB	n=100
10	Correct	23 ms	24228 KB	n=100
11	Correct	23 ms	24228 KB	n=100
12	Correct	21 ms	24228 KB	n=100
13	Correct	22 ms	24228 KB	n=100
14	Correct	21 ms	24228 KB	n=100
15	Correct	22 ms	24228 KB	n=100
16	Correct	22 ms	24240 KB	n=100
17	Correct	22 ms	24240 KB	n=100
18	Correct	21 ms	24244 KB	n=100
19	Correct	22 ms	24244 KB	n=100
20	Correct	21 ms	24244 KB	n=100
21	Correct	22 ms	24244 KB	n=100
22	Correct	23 ms	24244 KB	n=100
23	Correct	21 ms	24244 KB	n=100
24	Correct	21 ms	24244 KB	n=100
25	Correct	22 ms	24276 KB	n=100
26	Correct	21 ms	24276 KB	n=12
27	Correct	21 ms	24276 KB	n=100
28	Correct	25 ms	24376 KB	n=500
29	Correct	22 ms	24496 KB	n=500
30	Correct	23 ms	24496 KB	n=500
31	Correct	22 ms	24564 KB	n=500
32	Correct	23 ms	24564 KB	n=500
33	Correct	23 ms	24564 KB	n=500
34	Correct	22 ms	24564 KB	n=500
35	Correct	22 ms	24680 KB	n=500
36	Correct	22 ms	24680 KB	n=500
37	Correct	22 ms	24680 KB	n=500
38	Correct	30 ms	24680 KB	n=500
39	Correct	22 ms	24680 KB	n=500
40	Correct	22 ms	24680 KB	n=500
41	Correct	24 ms	24680 KB	n=500
42	Correct	23 ms	24680 KB	n=500
43	Correct	23 ms	24684 KB	n=500
44	Correct	21 ms	24696 KB	n=500
45	Correct	22 ms	24708 KB	n=500
46	Correct	22 ms	24720 KB	n=500
47	Correct	22 ms	24736 KB	n=500
48	Correct	22 ms	24772 KB	n=500
49	Correct	22 ms	24772 KB	n=500
50	Correct	21 ms	24780 KB	n=500
51	Correct	23 ms	24792 KB	n=500
52	Correct	23 ms	24808 KB	n=500
53	Correct	24 ms	24952 KB	n=500
54	Correct	24 ms	24952 KB	n=500
55	Correct	23 ms	24952 KB	n=278
56	Correct	24 ms	25072 KB	n=500
57	Correct	24 ms	25072 KB	n=500
58	Correct	23 ms	25072 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	n=5
2	Correct	21 ms	24060 KB	n=100
3	Correct	21 ms	24140 KB	n=100
4	Correct	20 ms	24140 KB	n=100
5	Correct	22 ms	24172 KB	n=100
6	Correct	22 ms	24172 KB	n=100
7	Correct	21 ms	24172 KB	n=100
8	Correct	21 ms	24228 KB	n=100
9	Correct	22 ms	24228 KB	n=100
10	Correct	23 ms	24228 KB	n=100
11	Correct	23 ms	24228 KB	n=100
12	Correct	21 ms	24228 KB	n=100
13	Correct	22 ms	24228 KB	n=100
14	Correct	21 ms	24228 KB	n=100
15	Correct	22 ms	24228 KB	n=100
16	Correct	22 ms	24240 KB	n=100
17	Correct	22 ms	24240 KB	n=100
18	Correct	21 ms	24244 KB	n=100
19	Correct	22 ms	24244 KB	n=100
20	Correct	21 ms	24244 KB	n=100
21	Correct	22 ms	24244 KB	n=100
22	Correct	23 ms	24244 KB	n=100
23	Correct	21 ms	24244 KB	n=100
24	Correct	21 ms	24244 KB	n=100
25	Correct	22 ms	24276 KB	n=100
26	Correct	21 ms	24276 KB	n=12
27	Correct	21 ms	24276 KB	n=100
28	Correct	25 ms	24376 KB	n=500
29	Correct	22 ms	24496 KB	n=500
30	Correct	23 ms	24496 KB	n=500
31	Correct	22 ms	24564 KB	n=500
32	Correct	23 ms	24564 KB	n=500
33	Correct	23 ms	24564 KB	n=500
34	Correct	22 ms	24564 KB	n=500
35	Correct	22 ms	24680 KB	n=500
36	Correct	22 ms	24680 KB	n=500
37	Correct	22 ms	24680 KB	n=500
38	Correct	30 ms	24680 KB	n=500
39	Correct	22 ms	24680 KB	n=500
40	Correct	22 ms	24680 KB	n=500
41	Correct	24 ms	24680 KB	n=500
42	Correct	23 ms	24680 KB	n=500
43	Correct	23 ms	24684 KB	n=500
44	Correct	21 ms	24696 KB	n=500
45	Correct	22 ms	24708 KB	n=500
46	Correct	22 ms	24720 KB	n=500
47	Correct	22 ms	24736 KB	n=500
48	Correct	22 ms	24772 KB	n=500
49	Correct	22 ms	24772 KB	n=500
50	Correct	21 ms	24780 KB	n=500
51	Correct	23 ms	24792 KB	n=500
52	Correct	23 ms	24808 KB	n=500
53	Correct	24 ms	24952 KB	n=500
54	Correct	24 ms	24952 KB	n=500
55	Correct	23 ms	24952 KB	n=278
56	Correct	24 ms	25072 KB	n=500
57	Correct	24 ms	25072 KB	n=500
58	Correct	23 ms	25072 KB	n=500
59	Correct	28 ms	25412 KB	n=2000
60	Correct	27 ms	25592 KB	n=2000
61	Correct	27 ms	25652 KB	n=2000
62	Correct	31 ms	25652 KB	n=2000
63	Correct	28 ms	25652 KB	n=2000
64	Correct	28 ms	25816 KB	n=2000
65	Correct	27 ms	25816 KB	n=2000
66	Correct	28 ms	25924 KB	n=2000
67	Correct	29 ms	25924 KB	n=2000
68	Correct	28 ms	25924 KB	n=2000
69	Correct	26 ms	25964 KB	n=2000
70	Correct	28 ms	26112 KB	n=2000
71	Correct	27 ms	26160 KB	n=2000
72	Correct	26 ms	26160 KB	n=2000
73	Correct	27 ms	26332 KB	n=2000
74	Correct	28 ms	26332 KB	n=1844
75	Correct	26 ms	26332 KB	n=2000
76	Correct	27 ms	26332 KB	n=2000
77	Correct	27 ms	26332 KB	n=2000
78	Correct	27 ms	26332 KB	n=2000
79	Correct	28 ms	26332 KB	n=2000
80	Correct	27 ms	26332 KB	n=2000
81	Correct	27 ms	26332 KB	n=2000
82	Correct	27 ms	26332 KB	n=2000
83	Correct	28 ms	26332 KB	n=2000
84	Correct	27 ms	26332 KB	n=2000
85	Correct	27 ms	26332 KB	n=2000
86	Correct	28 ms	26332 KB	n=2000
87	Correct	26 ms	26332 KB	n=2000
88	Correct	27 ms	26332 KB	n=2000
89	Correct	25 ms	26332 KB	n=2000
90	Correct	25 ms	26332 KB	n=2000
91	Correct	25 ms	26332 KB	n=2000

Subtask #4
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	n=5
2	Correct	21 ms	24060 KB	n=100
3	Correct	21 ms	24140 KB	n=100
4	Correct	20 ms	24140 KB	n=100
5	Correct	22 ms	24172 KB	n=100
6	Correct	22 ms	24172 KB	n=100
7	Correct	21 ms	24172 KB	n=100
8	Correct	21 ms	24228 KB	n=100
9	Correct	22 ms	24228 KB	n=100
10	Correct	23 ms	24228 KB	n=100
11	Correct	23 ms	24228 KB	n=100
12	Correct	21 ms	24228 KB	n=100
13	Correct	22 ms	24228 KB	n=100
14	Correct	21 ms	24228 KB	n=100
15	Correct	22 ms	24228 KB	n=100
16	Correct	22 ms	24240 KB	n=100
17	Correct	22 ms	24240 KB	n=100
18	Correct	21 ms	24244 KB	n=100
19	Correct	22 ms	24244 KB	n=100
20	Correct	21 ms	24244 KB	n=100
21	Correct	22 ms	24244 KB	n=100
22	Correct	23 ms	24244 KB	n=100
23	Correct	21 ms	24244 KB	n=100
24	Correct	21 ms	24244 KB	n=100
25	Correct	22 ms	24276 KB	n=100
26	Correct	21 ms	24276 KB	n=12
27	Correct	21 ms	24276 KB	n=100
28	Correct	25 ms	24376 KB	n=500
29	Correct	22 ms	24496 KB	n=500
30	Correct	23 ms	24496 KB	n=500
31	Correct	22 ms	24564 KB	n=500
32	Correct	23 ms	24564 KB	n=500
33	Correct	23 ms	24564 KB	n=500
34	Correct	22 ms	24564 KB	n=500
35	Correct	22 ms	24680 KB	n=500
36	Correct	22 ms	24680 KB	n=500
37	Correct	22 ms	24680 KB	n=500
38	Correct	30 ms	24680 KB	n=500
39	Correct	22 ms	24680 KB	n=500
40	Correct	22 ms	24680 KB	n=500
41	Correct	24 ms	24680 KB	n=500
42	Correct	23 ms	24680 KB	n=500
43	Correct	23 ms	24684 KB	n=500
44	Correct	21 ms	24696 KB	n=500
45	Correct	22 ms	24708 KB	n=500
46	Correct	22 ms	24720 KB	n=500
47	Correct	22 ms	24736 KB	n=500
48	Correct	22 ms	24772 KB	n=500
49	Correct	22 ms	24772 KB	n=500
50	Correct	21 ms	24780 KB	n=500
51	Correct	23 ms	24792 KB	n=500
52	Correct	23 ms	24808 KB	n=500
53	Correct	24 ms	24952 KB	n=500
54	Correct	24 ms	24952 KB	n=500
55	Correct	23 ms	24952 KB	n=278
56	Correct	24 ms	25072 KB	n=500
57	Correct	24 ms	25072 KB	n=500
58	Correct	23 ms	25072 KB	n=500
59	Correct	28 ms	25412 KB	n=2000
60	Correct	27 ms	25592 KB	n=2000
61	Correct	27 ms	25652 KB	n=2000
62	Correct	31 ms	25652 KB	n=2000
63	Correct	28 ms	25652 KB	n=2000
64	Correct	28 ms	25816 KB	n=2000
65	Correct	27 ms	25816 KB	n=2000
66	Correct	28 ms	25924 KB	n=2000
67	Correct	29 ms	25924 KB	n=2000
68	Correct	28 ms	25924 KB	n=2000
69	Correct	26 ms	25964 KB	n=2000
70	Correct	28 ms	26112 KB	n=2000
71	Correct	27 ms	26160 KB	n=2000
72	Correct	26 ms	26160 KB	n=2000
73	Correct	27 ms	26332 KB	n=2000
74	Correct	28 ms	26332 KB	n=1844
75	Correct	26 ms	26332 KB	n=2000
76	Correct	27 ms	26332 KB	n=2000
77	Correct	27 ms	26332 KB	n=2000
78	Correct	27 ms	26332 KB	n=2000
79	Correct	28 ms	26332 KB	n=2000
80	Correct	27 ms	26332 KB	n=2000
81	Correct	27 ms	26332 KB	n=2000
82	Correct	27 ms	26332 KB	n=2000
83	Correct	28 ms	26332 KB	n=2000
84	Correct	27 ms	26332 KB	n=2000
85	Correct	27 ms	26332 KB	n=2000
86	Correct	28 ms	26332 KB	n=2000
87	Correct	26 ms	26332 KB	n=2000
88	Correct	27 ms	26332 KB	n=2000
89	Correct	25 ms	26332 KB	n=2000
90	Correct	25 ms	26332 KB	n=2000
91	Correct	25 ms	26332 KB	n=2000
92	Correct	1205 ms	89380 KB	n=200000
93	Correct	1278 ms	92920 KB	n=200000
94	Correct	1277 ms	98932 KB	n=200000
95	Correct	1196 ms	98932 KB	n=200000
96	Correct	1209 ms	102728 KB	n=200000
97	Correct	1583 ms	113336 KB	n=200000
98	Correct	1303 ms	116884 KB	n=200000
99	Correct	1469 ms	123604 KB	n=200000
100	Correct	1251 ms	130480 KB	n=200000
101	Correct	1362 ms	146528 KB	n=200000
102	Correct	754 ms	146528 KB	n=200000
103	Correct	698 ms	146528 KB	n=200000
104	Correct	658 ms	146528 KB	n=200000
105	Correct	664 ms	146528 KB	n=200000
106	Correct	729 ms	146528 KB	n=200000
107	Correct	714 ms	146528 KB	n=200000
108	Correct	1252 ms	146528 KB	n=200000
109	Correct	1235 ms	146528 KB	n=200000
110	Correct	1246 ms	146528 KB	n=200000
111	Correct	1133 ms	146528 KB	n=200000
112	Correct	1302 ms	146528 KB	n=200000
113	Correct	1392 ms	146528 KB	n=200000
114	Correct	1195 ms	146528 KB	n=200000
115	Correct	1372 ms	146528 KB	n=200000
116	Correct	1150 ms	146528 KB	n=200000
117	Correct	1283 ms	154920 KB	n=200000
118	Correct	1529 ms	156852 KB	n=200000
119	Correct	1158 ms	161480 KB	n=200000
120	Correct	1130 ms	175968 KB	n=200000
121	Correct	1313 ms	175968 KB	n=200000
122	Correct	1143 ms	176468 KB	n=200000
123	Correct	688 ms	176468 KB	n=200000
124	Correct	257 ms	176468 KB	n=25264

답안 #85406

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 44.0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
44.0 / 44.0