제출 #90602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90602		GioChkhaidze	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1839 ms	128732 KiB

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;
			}
		}
	}	
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44