제출 #1100573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100573		vjudge1	Birthday gift (IZhO18_treearray)	C++17	56 / 100	26 ms	34196 KiB

treearray

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int N = 100001;

using namespace std;

ll n, m, k, a, b, c, e, d[N], bg[N], p[N], sz[N], h[N], up[N][22], tin[N], lc, sum, sum1, ans, mx[N], tout[N];
set <ll> s[N], st[N];
vector <ll> g[N];

void dfs (ll v, ll pp){
	up[v][0] = pp;
	sz[v] = 1;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pp){
			d[g[v][i]] = d[v] + 1;
			dfs (g[v][i], v);
		}
	}
}

ll lca (ll a, ll b){
	if (d[a] < d[b]){
		swap (a, b);
	}
	ll c = abs (d[a] - d[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb (a);
	}
	for (int i = 1; i <= m; i++){
		cin >> p[i];
	}
	dfs (1, 0);
	for (int i = 1; i < m; i++){
		st[p[i]].insert (i);
		s[lca (p[i], p[i + 1])].insert (i);
	}
	st[p[m]].insert(m);
	while (k--){
		cin >> a >> b >> c;
		if (a == 1){
			st[p[b]].erase (b);
			if (b != 1)s[lca (p[b], p[b - 1])].erase (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].erase (b);
			p[b] = c;
			st[p[b]].insert(b);
			if (b != 1)s[lca (p[b], p[b - 1])].insert (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].insert (b);
		}
		else{
			cin >> e;
			if (s[e].size() && *s[e].lower_bound(b) < c && *s[e].lower_bound(b) >= b){
				lc = *s[e].lower_bound(b);
				cout << lc << ' ' << lc + 1 << '\n';
			}
			else if (st[e].size() && *st[e].lower_bound(b) <= c && *st[e].lower_bound(b) >= b){
				cout << *st[e].lower_bound(b) << ' ' << *st[e].lower_bound (b) << '\n';
			}
			else{
				cout << "-1 -1\n";
			}
		}
	}
}

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

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

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