Submission #107133

#	Time	Username	Problem	Language	Result	Execution time	Memory
107133		Shafin666	Birthday gift (IZhO18_treearray)	C++14	100 / 100	3883 ms	102984 KiB

treearray

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>
#define  read_input         freopen("in.txt","r", stdin)
#define  print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 2e5+10, inf = 1e9+7;
set<int> S[maxn], T[maxn];
vector<int> adj[maxn];
int parent[20][maxn], level[maxn], a[maxn];

void dfs(int u, int par, int lev = 0) {
    level[u] = lev;
    parent[0][u] = par;

    for(auto it : adj[u]) 
        if(it != par) dfs(it, u, lev+1);
}

int lca(int u, int v) {
    if(level[u] < level[v]) swap(u, v);
    int i, k;
    
    if(level[u] != level[v]) {
        for(i = 19; i >= 0; i--) {
            if(parent[i][u] != -1 && level[parent[i][u]] >= level[v]) u = parent[i][u];
        }
    }
    if(u == v) return u;
    for(i = 19; i >= 0; i--) {
        if(parent[i][u] != -1 && parent[i][u] != parent[i][v]) {
            u = parent[i][u];
            v = parent[i][v];
        }
    } return parent[0][u];
}

int main()
{   
    int n, m, q;

    cin >> n >> m >> q;
    for(int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    } 

    memset(parent, -1, sizeof parent);
    dfs(1, -1);
    for(int i = 1; 1 << i < n; i++)
        for(int j = 1; j <= n; j++)
            if(parent[i-1][j] != -1) parent[i][j] = parent[i-1][parent[i-1][j]];

    for(int i = 1; i <= m; i++) {
        cin >> a[i];
        S[a[i]].insert(i);
        if(i > 1) T[lca(a[i], a[i-1])].insert(i);
    }
    
    for(int i = 1; i <= n; i++) S[i].insert(inf), T[i].insert(inf);

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

        if(ch == 1) {
            int pos, v;
            cin >> pos >> v;

            if(pos > 1) T[lca(a[pos], a[pos-1])].erase(pos);
            if(pos < m) T[lca(a[pos], a[pos+1])].erase(pos+1);

            S[a[pos]].erase(pos);
            a[pos] = v;
            S[a[pos]].insert(pos);

            if(pos > 1) T[lca(a[pos], a[pos-1])].insert(pos);
            if(pos < m) T[lca(a[pos], a[pos+1])].insert(pos+1);
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;

            int d = *S[v].lower_bound(l);
            int e = *T[v].lower_bound(l+1);

            if(d <= r) cout << d << ' ' << d << endl;
            else if(e <= r) cout << e-1 << ' ' << e << endl;
            else cout << -1 << ' ' << -1 << endl; 
        }
    }

    return 0;   
} 

Compilation message (stderr)

treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:26:12: warning: unused variable 'k' [-Wunused-variable]
     int i, k;
            ^

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