제출 #435542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435542		keta_tsimakuridze	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2016 ms	99596 KiB

treearray

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tmin[N],par[N][20],tmout[N],timer,n,m,q,a[N],Lg;
vector<int>V[N];
set<pair<int,int> >s[N];
void dfs(int u,int p) {
	tmin[u] = ++timer;
	par[u][0] = p;
	for(int i = 1;i<=Lg;i++) {
		par[u][i] = par[par[u][i-1]][i-1];
	}
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		dfs(V[u][i],u);
	}
	tmout[u] = timer;
}
bool check(int u,int v){
	if(tmin[u]<=tmin[v] && tmout[u]>=tmout[v]) return 1;
	return 0;
}
int find_lca(int u,int v){
	if(check(u,v)) return u;
	if(check(v,u)) return v;
	
	for(int i=Lg;i>=0;i--){
		if(par[u][i] && !check(par[u][i],v)) u = par[u][i];
	}

	return par[u][0];
}
 main(){
	cin>>n>>m>>q;
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	Lg = log2(n) + 1;
	dfs(1,0);
	for(int i=1;i<=m;i++) {
		cin >> a[i];
		if(i-1) {
			s[find_lca(a[i],a[i-1])].insert({i-1,i});
			
		}
		s[a[i]].insert({i,i});
	}
	while(q--) {
		cin>>t; 
		if(t==1) {
			int i,val;
			cin>>i>>val;
			s[a[i]].erase({i,i});
			if(i-1) {
				int lca = find_lca(a[i],a[i-1]);
				s[find_lca(a[i],a[i-1])].erase({i-1,i});
				s[find_lca(val,a[i-1])].insert({i-1,i});
				
			}
			if(i<m) {
				int lca = find_lca(a[i],a[i+1]);
				s[find_lca(a[i],a[i+1])].erase({i,i+1});
				s[find_lca(val,a[i+1])].insert({i,i+1});
			}	
			a[i] = val;
			s[a[i]].insert({i,i});
			
		}
		else {
			int u,l,r;
			cin>>l>>r>>u;
			if(!s[u].size() || s[u].upper_bound({l,0})==s[u].end() || (*s[u].upper_bound({l,0})).s>r) {
				cout<<"-1 -1"<<endl;
			}
			else cout<<(*s[u].upper_bound({l,0})).f<<" "<<(*s[u].upper_bound({l,0})).s<<endl;
		} 
	}
}

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

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:16:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
treearray.cpp: At global scope:
treearray.cpp:36:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 |  main(){
      |  ^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:61:9: warning: unused variable 'lca' [-Wunused-variable]
   61 |     int lca = find_lca(a[i],a[i-1]);
      |         ^~~
treearray.cpp:67:9: warning: unused variable 'lca' [-Wunused-variable]
   67 |     int lca = find_lca(a[i],a[i+1]);
      |         ^~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44