Submission #797403

#	Time	Username	Problem	Language	Result	Execution time	Memory
797403		kingfran1907	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1055 ms	74112 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int logo = 20;

int n, m, q;
vector< int > graph[maxn];
int dp[logo + 10][maxn];
int dis[maxn];
int niz[maxn];
set< pair<int, int> > qs[maxn];

void dfs(int x, int parr) {
	dp[0][x] = parr;
	dis[x] = 1 + dis[parr];
	
	for (int tren : graph[x]) {
		if (tren != parr) dfs(tren, x);
	}
}

int lif(int x, int val) {
	for (int i = 0; i < logo; i++)
		if (val & (1 << i)) x = dp[i][x];
	return x;
}

int lca(int a, int b) {
	if (dis[a] > dis[b]) a = lif(a, dis[a] - dis[b]);
	else b = lif(b, dis[b] - dis[a]);
	if (a == b) return a;
	
	for (int i = logo - 1; i >= 0; i--) {
		if (dp[i][a] != dp[i][b]) {
			a = dp[i][a];
			b = dp[i][b];
		}
	}
	return dp[0][a];
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	dfs(1, 0);
	for (int i = 1; i < logo; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
	
	for (int i = 0; i < m; i++) {
		scanf("%d", niz+i);
		qs[niz[i]].insert({i, i});
		if (i > 0) qs[lca(niz[i - 1], niz[i])].insert({i - 1, i});
	}
	
	while (q--) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			int x, v;
			scanf("%d%d", &x, &v); x--;
			qs[niz[x]].erase({x, x});
			if (x > 0) qs[lca(niz[x - 1], niz[x])].erase({x - 1, x});
			if (x < m - 1) qs[lca(niz[x], niz[x + 1])].erase({x, x + 1});
			
			niz[x] = v;
			qs[niz[x]].insert({x, x});
			if (x > 0) qs[lca(niz[x - 1], niz[x])].insert({x - 1, x});
			if (x < m - 1) qs[lca(niz[x], niz[x + 1])].insert({x, x + 1});
		} else {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v); l--, r--;
			auto iter = qs[v].lower_bound({l, l});
			if (iter == qs[v].end() || iter->second > r) printf("-1 -1\n");
			else printf("%d %d\n", iter->first + 1, iter->second + 1);
		}
	}
	return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
treearray.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf("%d%d", &x, &v); x--;
      |    ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d%d%d", &l, &r, &v); l--, r--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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