Submission #492381

#	Time	Username	Problem	Language	Result	Execution time	Memory
492381		Mike4235	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1119 ms	93636 KiB

treearray

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, m, q;
int a[200005], d[200005], up[200005][18];
pii res;
set<int> id[200005], se[200005];
vector<int> g[200005];

void dfs(int u, int p) {
    for1(i,1,17) up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : g[u]) if (v != p) {
        d[v] = d[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);

    for1(i,0,17) if ((d[u] - d[v]) & (1 << i)) u = up[u][i];
    if (u == v) return u;
    
    for2(i,17,0) if (up[u][i] != up[v][i]) {
        u = up[u][i];
        v = up[v][i];
    }

    return up[u][0];
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> m >> q;
    for1(i,1,n - 1) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);
    for1(i,1,m) {
        cin >> a[i];
        id[a[i]].insert(i);
    }

    for1(i,1,m - 1) se[lca(a[i], a[i + 1])].insert(i);

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int i, u;
            cin >> i >> u;
            id[a[i]].erase(i);
            if (i > 1) se[lca(a[i - 1], a[i])].erase(i - 1);
            if (i < m) se[lca(a[i], a[i + 1])].erase(i);
            a[i] = u;
            id[a[i]].insert(i);
            if (i > 1) se[lca(a[i - 1], a[i])].insert(i - 1);
            if (i < m) se[lca(a[i], a[i + 1])].insert(i);
        }
        else {
            int l, r, u;
            cin >> l >> r >> u;

            auto it = id[u].lower_bound(l);
            if (it != id[u].end() && *it <= r) {
                cout << *it << " " << *it << "\n";
                continue;
            }

            auto it2 = se[u].lower_bound(l);
            if (it2 != se[u].end() && *it2 < r) {
                cout << *it2 << " " << *it2 + 1 << "\n";
                continue;
            }

            cout << "-1 -1\n";
        }
    }
    
}

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