oj.uz

Submission #797378

# Submission time Handle Problem Language Result Execution time Memory
797378 2023-07-29T10:11:03 Z kingfran1907 Birthday gift (IZhO18_treearray) C++14
0 / 100
 2 ms 5076 KB 
#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];
map< int, set< pair<int, int> > > qs;

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]);
	
	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

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

Subtask #1
0 / 12.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 44.0

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