답안 #90602 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90602	2018-12-22T20:27:20 Z	GioChkhaidze	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1839 ms	128732 KB

treearray

#include <bits/stdc++.h>

#define Tree int h,int l,int r,int L,int R
#define left 2*h,l,(l+r)/2,L,R
#define right 2*h+1,(l+r)/2+1,r,L,R

#define F first
#define S second
#define Pb push_back

using namespace std;

int n,m,q,A,B,depth,type,l,r,val,pos;

vector < int > v [ 200005 ] ;

int dep[200005],P[200005][25],a[200005],b[200005];

set < int > st[200005];
set < int > St[200005];

const int lg=23;

void Dfs(int x,int p)
{
	dep[x]=++depth;
	P[x][0]=p;	
	
	for (int i=0; i<v[x].size(); i++)
	{
		if (v[x][i]==p) continue;
		Dfs(v[x][i],x);
	}
	
	depth--;
}

int LCA(int a,int b)
{
	if (dep[a]<dep[b]) swap(a,b);
	
	if (a==b) return a;
	
	for (int i=lg; i>=0; i--)
		if (dep[P[a][i]]>=dep[b]) a=P[a][i];
	
	if (a==b) return a;
	
	for (int i=lg; i>=0; i--)
		if (P[a][i]!=P[b][i])
		{
			a=P[a][i];
			b=P[b][i];
		}
		
	return P[a][0];
}

main ()
{
	ios::sync_with_stdio(0);
	
	cin>>n>>m>>q;
	
	for (int i=1; i<n; i++)
	{
		cin>>A>>B;
		
		v[A].Pb(B);
		v[B].Pb(A);
	}
	
	Dfs(1,1);
	
	for (int j=1; j<=lg; j++)
		for (int i=1; i<=n; i++)
			P[i][j]=P[P[i][j-1]][j-1];
	
	for (int i=1; i<=m; i++)
	{
		cin>>a[i];
		
		St[a[i]].insert(i);
		
		if (i==1) continue;
		
		b[i]=LCA(a[i],a[i-1]);
	
		st[b[i]].insert(i);
	}

	for (int i=1; i<=q; i++)
	{
		cin>>type;
		
		if (type==1)
		{
			cin>>pos>>val;
			
			St[a[pos]].erase(St[a[pos]].find(pos));
			
			a[pos]=val;
			
			St[a[pos]].insert(pos);
		
			
			if (pos!=m)
			{
				st[b[pos+1]].erase(st[b[pos+1]].find(pos+1));
				
				b[pos+1]=LCA(a[pos],a[pos+1]);
			
				st[b[pos+1]].insert(pos+1);
			}
			
			if (pos!=1) 
			{
				st[b[pos]].erase(st[b[pos]].find(pos));
				b[pos]=LCA(a[pos],a[pos-1]);
				st[b[pos]].insert(pos);
			}
		}
			else
		if (type==2)
		{
			cin>>l>>r>>val;
			
			if (St[val].lower_bound(l)!=St[val].end())
			{
				int idx=*St[val].lower_bound(l);
				
				if (idx<=r) 
				{
					cout<<idx<<" "<<idx<<endl;
					continue;
				}
			}
			
			if (st[val].lower_bound(l+1)==st[val].end()) cout<<"-1 -1"<<endl;
				else
			{
				int idx=*st[val].lower_bound(l+1);
		
				if (idx>r) cout<<"-1 -1"<<endl;
					else cout<<idx-1<<" "<<idx<<endl;
			}
		}
	}	
}

Compilation message

treearray.cpp: In function 'void Dfs(int, int)':
treearray.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++)
                ~^~~~~~~~~~~~
treearray.cpp: At global scope:
treearray.cpp:59:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23800 KB	n=5
2	Correct	22 ms	23924 KB	n=100
3	Correct	23 ms	23944 KB	n=100
4	Correct	23 ms	23944 KB	n=100
5	Correct	24 ms	23988 KB	n=100
6	Correct	24 ms	23988 KB	n=100
7	Correct	23 ms	23988 KB	n=100
8	Correct	21 ms	23988 KB	n=100
9	Correct	23 ms	23988 KB	n=100
10	Correct	23 ms	23988 KB	n=100
11	Correct	24 ms	24052 KB	n=100
12	Correct	23 ms	24088 KB	n=100
13	Correct	23 ms	24136 KB	n=100
14	Correct	19 ms	24136 KB	n=100
15	Correct	23 ms	24136 KB	n=100
16	Correct	19 ms	24136 KB	n=100
17	Correct	19 ms	24136 KB	n=100
18	Correct	19 ms	24136 KB	n=100
19	Correct	19 ms	24136 KB	n=100
20	Correct	19 ms	24136 KB	n=100
21	Correct	23 ms	24136 KB	n=100
22	Correct	19 ms	24152 KB	n=100
23	Correct	18 ms	24152 KB	n=100
24	Correct	19 ms	24152 KB	n=100
25	Correct	19 ms	24152 KB	n=100
26	Correct	19 ms	24152 KB	n=12
27	Correct	18 ms	24152 KB	n=100

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23800 KB	n=5
2	Correct	22 ms	23924 KB	n=100
3	Correct	23 ms	23944 KB	n=100
4	Correct	23 ms	23944 KB	n=100
5	Correct	24 ms	23988 KB	n=100
6	Correct	24 ms	23988 KB	n=100
7	Correct	23 ms	23988 KB	n=100
8	Correct	21 ms	23988 KB	n=100
9	Correct	23 ms	23988 KB	n=100
10	Correct	23 ms	23988 KB	n=100
11	Correct	24 ms	24052 KB	n=100
12	Correct	23 ms	24088 KB	n=100
13	Correct	23 ms	24136 KB	n=100
14	Correct	19 ms	24136 KB	n=100
15	Correct	23 ms	24136 KB	n=100
16	Correct	19 ms	24136 KB	n=100
17	Correct	19 ms	24136 KB	n=100
18	Correct	19 ms	24136 KB	n=100
19	Correct	19 ms	24136 KB	n=100
20	Correct	19 ms	24136 KB	n=100
21	Correct	23 ms	24136 KB	n=100
22	Correct	19 ms	24152 KB	n=100
23	Correct	18 ms	24152 KB	n=100
24	Correct	19 ms	24152 KB	n=100
25	Correct	19 ms	24152 KB	n=100
26	Correct	19 ms	24152 KB	n=12
27	Correct	18 ms	24152 KB	n=100
28	Correct	20 ms	24264 KB	n=500
29	Correct	19 ms	24276 KB	n=500
30	Correct	25 ms	24292 KB	n=500
31	Correct	24 ms	24308 KB	n=500
32	Correct	24 ms	24324 KB	n=500
33	Correct	22 ms	24336 KB	n=500
34	Correct	24 ms	24352 KB	n=500
35	Correct	23 ms	24364 KB	n=500
36	Correct	27 ms	24380 KB	n=500
37	Correct	24 ms	24392 KB	n=500
38	Correct	20 ms	24404 KB	n=500
39	Correct	20 ms	24416 KB	n=500
40	Correct	24 ms	24508 KB	n=500
41	Correct	24 ms	24508 KB	n=500
42	Correct	24 ms	24508 KB	n=500
43	Correct	25 ms	24508 KB	n=500
44	Correct	24 ms	24508 KB	n=500
45	Correct	24 ms	24508 KB	n=500
46	Correct	23 ms	24512 KB	n=500
47	Correct	24 ms	24528 KB	n=500
48	Correct	24 ms	24544 KB	n=500
49	Correct	24 ms	24556 KB	n=500
50	Correct	24 ms	24572 KB	n=500
51	Correct	24 ms	24588 KB	n=500
52	Correct	23 ms	24760 KB	n=500
53	Correct	24 ms	24760 KB	n=500
54	Correct	23 ms	24760 KB	n=500
55	Correct	24 ms	24760 KB	n=278
56	Correct	24 ms	24760 KB	n=500
57	Correct	24 ms	24760 KB	n=500
58	Correct	25 ms	24760 KB	n=500

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23800 KB	n=5
2	Correct	22 ms	23924 KB	n=100
3	Correct	23 ms	23944 KB	n=100
4	Correct	23 ms	23944 KB	n=100
5	Correct	24 ms	23988 KB	n=100
6	Correct	24 ms	23988 KB	n=100
7	Correct	23 ms	23988 KB	n=100
8	Correct	21 ms	23988 KB	n=100
9	Correct	23 ms	23988 KB	n=100
10	Correct	23 ms	23988 KB	n=100
11	Correct	24 ms	24052 KB	n=100
12	Correct	23 ms	24088 KB	n=100
13	Correct	23 ms	24136 KB	n=100
14	Correct	19 ms	24136 KB	n=100
15	Correct	23 ms	24136 KB	n=100
16	Correct	19 ms	24136 KB	n=100
17	Correct	19 ms	24136 KB	n=100
18	Correct	19 ms	24136 KB	n=100
19	Correct	19 ms	24136 KB	n=100
20	Correct	19 ms	24136 KB	n=100
21	Correct	23 ms	24136 KB	n=100
22	Correct	19 ms	24152 KB	n=100
23	Correct	18 ms	24152 KB	n=100
24	Correct	19 ms	24152 KB	n=100
25	Correct	19 ms	24152 KB	n=100
26	Correct	19 ms	24152 KB	n=12
27	Correct	18 ms	24152 KB	n=100
28	Correct	20 ms	24264 KB	n=500
29	Correct	19 ms	24276 KB	n=500
30	Correct	25 ms	24292 KB	n=500
31	Correct	24 ms	24308 KB	n=500
32	Correct	24 ms	24324 KB	n=500
33	Correct	22 ms	24336 KB	n=500
34	Correct	24 ms	24352 KB	n=500
35	Correct	23 ms	24364 KB	n=500
36	Correct	27 ms	24380 KB	n=500
37	Correct	24 ms	24392 KB	n=500
38	Correct	20 ms	24404 KB	n=500
39	Correct	20 ms	24416 KB	n=500
40	Correct	24 ms	24508 KB	n=500
41	Correct	24 ms	24508 KB	n=500
42	Correct	24 ms	24508 KB	n=500
43	Correct	25 ms	24508 KB	n=500
44	Correct	24 ms	24508 KB	n=500
45	Correct	24 ms	24508 KB	n=500
46	Correct	23 ms	24512 KB	n=500
47	Correct	24 ms	24528 KB	n=500
48	Correct	24 ms	24544 KB	n=500
49	Correct	24 ms	24556 KB	n=500
50	Correct	24 ms	24572 KB	n=500
51	Correct	24 ms	24588 KB	n=500
52	Correct	23 ms	24760 KB	n=500
53	Correct	24 ms	24760 KB	n=500
54	Correct	23 ms	24760 KB	n=500
55	Correct	24 ms	24760 KB	n=278
56	Correct	24 ms	24760 KB	n=500
57	Correct	24 ms	24760 KB	n=500
58	Correct	25 ms	24760 KB	n=500
59	Correct	25 ms	25076 KB	n=2000
60	Correct	30 ms	25276 KB	n=2000
61	Correct	28 ms	25276 KB	n=2000
62	Correct	29 ms	25288 KB	n=2000
63	Correct	27 ms	25448 KB	n=2000
64	Correct	29 ms	25516 KB	n=2000
65	Correct	29 ms	25516 KB	n=2000
66	Correct	28 ms	25752 KB	n=2000
67	Correct	28 ms	25752 KB	n=2000
68	Correct	27 ms	25752 KB	n=2000
69	Correct	28 ms	25752 KB	n=2000
70	Correct	28 ms	25752 KB	n=2000
71	Correct	25 ms	25780 KB	n=2000
72	Correct	28 ms	25836 KB	n=2000
73	Correct	28 ms	25908 KB	n=2000
74	Correct	26 ms	25948 KB	n=1844
75	Correct	28 ms	25992 KB	n=2000
76	Correct	29 ms	26048 KB	n=2000
77	Correct	29 ms	26200 KB	n=2000
78	Correct	29 ms	26200 KB	n=2000
79	Correct	29 ms	26204 KB	n=2000
80	Correct	28 ms	26380 KB	n=2000
81	Correct	28 ms	26436 KB	n=2000
82	Correct	28 ms	26436 KB	n=2000
83	Correct	29 ms	26540 KB	n=2000
84	Correct	29 ms	26540 KB	n=2000
85	Correct	25 ms	26648 KB	n=2000
86	Correct	25 ms	26704 KB	n=2000
87	Correct	24 ms	26704 KB	n=2000
88	Correct	25 ms	26812 KB	n=2000
89	Correct	23 ms	26860 KB	n=2000
90	Correct	42 ms	26980 KB	n=2000
91	Correct	25 ms	26980 KB	n=2000

Subtask #4
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23800 KB	n=5
2	Correct	22 ms	23924 KB	n=100
3	Correct	23 ms	23944 KB	n=100
4	Correct	23 ms	23944 KB	n=100
5	Correct	24 ms	23988 KB	n=100
6	Correct	24 ms	23988 KB	n=100
7	Correct	23 ms	23988 KB	n=100
8	Correct	21 ms	23988 KB	n=100
9	Correct	23 ms	23988 KB	n=100
10	Correct	23 ms	23988 KB	n=100
11	Correct	24 ms	24052 KB	n=100
12	Correct	23 ms	24088 KB	n=100
13	Correct	23 ms	24136 KB	n=100
14	Correct	19 ms	24136 KB	n=100
15	Correct	23 ms	24136 KB	n=100
16	Correct	19 ms	24136 KB	n=100
17	Correct	19 ms	24136 KB	n=100
18	Correct	19 ms	24136 KB	n=100
19	Correct	19 ms	24136 KB	n=100
20	Correct	19 ms	24136 KB	n=100
21	Correct	23 ms	24136 KB	n=100
22	Correct	19 ms	24152 KB	n=100
23	Correct	18 ms	24152 KB	n=100
24	Correct	19 ms	24152 KB	n=100
25	Correct	19 ms	24152 KB	n=100
26	Correct	19 ms	24152 KB	n=12
27	Correct	18 ms	24152 KB	n=100
28	Correct	20 ms	24264 KB	n=500
29	Correct	19 ms	24276 KB	n=500
30	Correct	25 ms	24292 KB	n=500
31	Correct	24 ms	24308 KB	n=500
32	Correct	24 ms	24324 KB	n=500
33	Correct	22 ms	24336 KB	n=500
34	Correct	24 ms	24352 KB	n=500
35	Correct	23 ms	24364 KB	n=500
36	Correct	27 ms	24380 KB	n=500
37	Correct	24 ms	24392 KB	n=500
38	Correct	20 ms	24404 KB	n=500
39	Correct	20 ms	24416 KB	n=500
40	Correct	24 ms	24508 KB	n=500
41	Correct	24 ms	24508 KB	n=500
42	Correct	24 ms	24508 KB	n=500
43	Correct	25 ms	24508 KB	n=500
44	Correct	24 ms	24508 KB	n=500
45	Correct	24 ms	24508 KB	n=500
46	Correct	23 ms	24512 KB	n=500
47	Correct	24 ms	24528 KB	n=500
48	Correct	24 ms	24544 KB	n=500
49	Correct	24 ms	24556 KB	n=500
50	Correct	24 ms	24572 KB	n=500
51	Correct	24 ms	24588 KB	n=500
52	Correct	23 ms	24760 KB	n=500
53	Correct	24 ms	24760 KB	n=500
54	Correct	23 ms	24760 KB	n=500
55	Correct	24 ms	24760 KB	n=278
56	Correct	24 ms	24760 KB	n=500
57	Correct	24 ms	24760 KB	n=500
58	Correct	25 ms	24760 KB	n=500
59	Correct	25 ms	25076 KB	n=2000
60	Correct	30 ms	25276 KB	n=2000
61	Correct	28 ms	25276 KB	n=2000
62	Correct	29 ms	25288 KB	n=2000
63	Correct	27 ms	25448 KB	n=2000
64	Correct	29 ms	25516 KB	n=2000
65	Correct	29 ms	25516 KB	n=2000
66	Correct	28 ms	25752 KB	n=2000
67	Correct	28 ms	25752 KB	n=2000
68	Correct	27 ms	25752 KB	n=2000
69	Correct	28 ms	25752 KB	n=2000
70	Correct	28 ms	25752 KB	n=2000
71	Correct	25 ms	25780 KB	n=2000
72	Correct	28 ms	25836 KB	n=2000
73	Correct	28 ms	25908 KB	n=2000
74	Correct	26 ms	25948 KB	n=1844
75	Correct	28 ms	25992 KB	n=2000
76	Correct	29 ms	26048 KB	n=2000
77	Correct	29 ms	26200 KB	n=2000
78	Correct	29 ms	26200 KB	n=2000
79	Correct	29 ms	26204 KB	n=2000
80	Correct	28 ms	26380 KB	n=2000
81	Correct	28 ms	26436 KB	n=2000
82	Correct	28 ms	26436 KB	n=2000
83	Correct	29 ms	26540 KB	n=2000
84	Correct	29 ms	26540 KB	n=2000
85	Correct	25 ms	26648 KB	n=2000
86	Correct	25 ms	26704 KB	n=2000
87	Correct	24 ms	26704 KB	n=2000
88	Correct	25 ms	26812 KB	n=2000
89	Correct	23 ms	26860 KB	n=2000
90	Correct	42 ms	26980 KB	n=2000
91	Correct	25 ms	26980 KB	n=2000
92	Correct	1089 ms	81968 KB	n=200000
93	Correct	1804 ms	90568 KB	n=200000
94	Correct	1689 ms	93976 KB	n=200000
95	Correct	1306 ms	93976 KB	n=200000
96	Correct	1217 ms	98228 KB	n=200000
97	Correct	1733 ms	107348 KB	n=200000
98	Correct	1260 ms	107348 KB	n=200000
99	Correct	1517 ms	107348 KB	n=200000
100	Correct	1286 ms	107348 KB	n=200000
101	Correct	1608 ms	113292 KB	n=200000
102	Correct	937 ms	113292 KB	n=200000
103	Correct	787 ms	113292 KB	n=200000
104	Correct	757 ms	113292 KB	n=200000
105	Correct	916 ms	117428 KB	n=200000
106	Correct	924 ms	120760 KB	n=200000
107	Correct	869 ms	120760 KB	n=200000
108	Correct	1306 ms	120760 KB	n=200000
109	Correct	1401 ms	120760 KB	n=200000
110	Correct	1443 ms	120760 KB	n=200000
111	Correct	1266 ms	120760 KB	n=200000
112	Correct	1718 ms	127556 KB	n=200000
113	Correct	1553 ms	127556 KB	n=200000
114	Correct	1039 ms	127556 KB	n=200000
115	Correct	1839 ms	127556 KB	n=200000
116	Correct	1174 ms	127556 KB	n=200000
117	Correct	1555 ms	127812 KB	n=200000
118	Correct	1415 ms	127812 KB	n=200000
119	Correct	994 ms	127812 KB	n=200000
120	Correct	1211 ms	128208 KB	n=200000
121	Correct	1236 ms	128208 KB	n=200000
122	Correct	1342 ms	128732 KB	n=200000
123	Correct	829 ms	128732 KB	n=200000
124	Correct	297 ms	128732 KB	n=25264

답안 #90602

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