oj.uz

Submission #651274

# Submission time Handle Problem Language Result Execution time Memory
651274 2022-10-18T05:35:42 Z becaido Birthday gift (IZhO18_treearray) C++17
0 / 100
 9 ms 14420 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int H = __lg (SIZE) + 1;

int n, m, q;
vector<int> adj[SIZE];
int h[SIZE], to[SIZE][H + 1];
int a[SIZE];
multiset<int> ms[SIZE];

void dfs (int pos, int fa) {
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        dfs (np, pos);
    }
}

int jump (int pos, int k) {
    int c = 0;
    while (k) {
        if (k & 1) pos = to[pos][c];
        k >>= 1;
        c++;
    }
    return pos;
}

int lca (int a, int b) {
    if (h[a] < h[b]) swap (a, b);
    a = jump (a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    h[1] = 1;
    dfs (1, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];
    FOR (i, 1, m) {
        cin >> a[i];
        ms[a[i]].insert (i);
    }
    FOR (i, 2, m) {
        ms[lca (a[i - 1], a[i])].insert (i);
    }
    while (q--) {
        int ty, p, x, l, r, lc;
        cin >> ty;
        if (ty == 1) {
            cin >> p >> x;
            ms[a[p]].erase (ms[a[p]].find (p));
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].erase (ms[lc].find (p));
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].erase (ms[lc].find (p + 1));
            }
            a[p] = x;
            ms[a[p]].insert (p);
            if (p > 1) {
                lc = lca (a[p - 1], a[p]);
                ms[lc].insert (p);
            }
            if (p < m) {
                lc = lca (a[p], a[p + 1]);
                ms[lc].insert (p + 1);
            }
        } else {
            cin >> l >> r >> x;
            auto it = ms[x].lower_bound (l);
            if (it == ms[x].end() || *it > r) {
                cout << "-1 -1\n";
                continue;
            }
            p = *it;
            if (a[p] == x) cout << p << ' ' << p << '\n';
            else if (p - 1 >= l && lca (a[p - 1], a[p]) == x) cout << p - 1 << ' ' << p << '\n';
            else cout << "-1 -1\n";
        }
    }
}

int main() {
    Waimai;
    solve();
}

/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Incorrect 9 ms 14420 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Incorrect 9 ms 14420 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Incorrect 9 ms 14420 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB n=5
2 Incorrect 9 ms 14420 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -