Submission #50911

#	Time	Username	Problem	Language	Result	Execution time	Memory
50911		Nicksechko	Birthday gift (IZhO18_treearray)	C++14	100 / 100	3233 ms	300008 KiB

treearray

#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int LOG = 20;
const int MAXN = 220000;

int tin[MAXN];
int tout[MAXN];

int up[LOG][MAXN];

vector<int> eds[MAXN];
set<int> g1[MAXN];
set<int> g2[MAXN];
int tm1;
int a[MAXN];

int n, m, q;

void dfs1(int v, int p) {
	tin[v] = tm1++;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		up[0][u] = v;
		dfs1(u, v);
	}
	tout[v] = tm1;
}

int is_p(int a, int b) {
	return tin[a] <= tin[b] && tin[b] < tout[a];
}

int lca(int a, int b) {
	if (is_p(a, b))
		return a;
	for (int i = LOG - 1; i >= 0; --i) {
		if (!is_p(up[i][a], b))
			a = up[i][a];
	}
	return up[0][a];
}


int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d", a + i);
		--a[i];
	}
	dfs1(0, -1);
	for (int i = 1; i < LOG; ++i) {
		for (int j = 0; j < n; ++j)
			up[i][j] = up[i - 1][up[i - 1][j]];
	}
	for (int i = 0; i < m; ++i) {
		g1[a[i]].insert(i);
		if (i < m - 1)
			g2[lca(a[i], a[i + 1])].insert(i);
	}
	for (int i = 0; i < q; ++i) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			int ps, v;
			scanf("%d%d", &ps, &v);
			--ps, --v;
			g1[a[ps]].erase(ps);
			if (ps < m - 1)
				g2[lca(a[ps], a[ps + 1])].erase(ps);
			if (ps > 0)
				g2[lca(a[ps], a[ps - 1])].erase(ps - 1);
			a[ps] = v;
			g1[a[ps]].insert(ps);
			if (ps < m - 1)
				g2[lca(a[ps], a[ps + 1])].insert(ps);
			if (ps > 0)
				g2[lca(a[ps], a[ps - 1])].insert(ps - 1);
		}
		else {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v);
			--l, --r, --v;
			auto it1 = g1[v].lower_bound(l);
			if (it1 != g1[v].end() && *it1 <= r) {
				printf("%d %d\n", *it1 + 1, *it1 + 1);
			}
			else {
				auto it2 = g2[v].lower_bound(l);
				if (it2 != g2[v].end() && *it2 < r) {
					printf("%d %d\n", *it2 + 1, *it2 + 1 + 1);
				}
				else {
					printf("-1 -1\n");
				}
			}
		}
	}
	return 0;
}

Compilation message (stderr)

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

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