Submission #1126174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126174		blackslex	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1222 ms	76632 KiB

treearray

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int N = 2e5 + 5, K = 20;
int n, m, q, x, y, z, w, a[N], dep[N], dp[K][N];
vector<int> v[N];
set<int> s[N], s2[N];

void dfs (int cur, int par) {
    dp[0][cur] = par; dep[cur] = dep[par] + 1;
    for (auto &e: v[cur]) {
        if (par == e) continue;
        dfs(e, cur);
    }
}

int lca (int a, int b) {
    if (dep[b] > dep[a]) swap(a, b);
    for (int i = K - 1; i >= 0; i--) if (dep[dp[i][a]] >= dep[b]) a = dp[i][a];
    if (a == b) return a;
    for (int i = K - 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++) {
        scanf("%d %d", &x, &y);
        v[x].emplace_back(y);
        v[y].emplace_back(x);
    }
    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    dfs(1, 0);
    for (int i = 1; i < K; i++) {
        for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
    for (int i = 1; i <= m; i++) s[a[i]].emplace(i);
    for (int i = 1; i < m; i++) s2[lca(a[i], a[i + 1])].emplace(i);
    while (q--) {
        scanf("%d %d %d", &x, &y, &z);
        if (x == 1) {
            s[a[y]].erase(y);
            if (y < m) s2[lca(a[y], a[y + 1])].erase(y);
            if (y > 1) s2[lca(a[y - 1], a[y])].erase(y - 1);
            s[a[y] = z].emplace(y);
            if (y < m) s2[lca(a[y], a[y + 1])].emplace(y);
            if (y > 1) s2[lca(a[y - 1], a[y])].emplace(y - 1);
        } else {
            scanf("%d", &w);
            auto it = s[w].lower_bound(y);
            if (*it <= z && it != s[w].end()) {
                printf("%d %d\n", *it, *it);
                continue;
            }
            auto it2 = s2[w].lower_bound(y);
            if (*it2 + 1 <= z && it2 != s2[w].end()) {
                printf("%d %d\n", *it2, *it2 + 1);
                continue;
            }
            printf("-1 -1\n");
        }
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:34:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
treearray.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d", &w);
      |             ~~~~~^~~~~~~~~~

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