oj.uz

Submission #90601

# Submission time Handle Problem Language Result Execution time Memory
90601 2018-12-22T20:24:23 Z GioChkhaidze Birthday gift (IZhO18_treearray) C++14
0 / 100
 23 ms 24060 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>=1; i--)
		if (dep[P[a][i]]!=dep[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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB n=5
2 Incorrect 23 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB n=5
2 Incorrect 23 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB n=5
2 Incorrect 23 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB n=5
2 Incorrect 23 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -