oj.uz

Submission #90602

# Submission time Handle Problem Language Result Execution time Memory
90602 2018-12-22T20:27:20 Z GioChkhaidze Birthday gift (IZhO18_treearray) C++14
100 / 100
 1839 ms 128732 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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