Submission #345428

#	Time	Username	Problem	Language	Result	Execution time	Memory
345428		koketsu	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4046 ms	64676 KiB

treearray

    #include <bits/stdc++.h>
    #define pb push_back
    #define LL long long
    #define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    using namespace std;

    const LL Mxn = 1e6 + 7;
    const LL Mod = 1e9 + 7;
    const LL Inf = 1e14 + 7;

    int N, M, Q, d[Mxn][20], lvl[Mxn], LCA[Mxn], W[Mxn];

    vector <int> g[Mxn];

    void Dfs(int x, int p){
        d[x][0] = p;
        lvl[x] = lvl[p] + 1;
        for(int i = 1; i <= 18; i++){
            d[x][i] = d[d[x][i - 1]][i - 1];
        }
        for(int to : g[x]){
            if(to == p) continue;
            Dfs(to, x);
        }
    }

    int lca(int u, int v){
        if(lvl[u] < lvl[v]) swap(u, v);
        int dif = (lvl[u] - lvl[v]);
        for(int i = 0; i <= 18; i++){
            if((1 << i) & dif) u = d[u][i];
        }
        if(u == v) return u;
        for(int i = 18; i >= 0; i--){
            if(d[u][i] != d[v][i]) u = d[u][i], v = d[v][i];
        }
        return d[u][0];
    }

    int main(){
        Kultivator;
        cin >> N >> M >> Q;
        for(int i = 1, A, B; i < N; i++){
            cin >> A >> B;
            g[A].pb(B);
            g[B].pb(A);
        }
        for(int i = 1; i <= M; i++){
            cin >> W[i];
        }
        Dfs(1, 0);
        for(int i = 1; i < M; i++){
            LCA[i] = lca(W[i], W[i + 1]);
        }
        while(Q--){
            int T;
            cin >> T;
            if(T == 1){
                int Pos, v;
                cin >> Pos >> v;
                W[Pos] = v;
                if(Pos > 1) LCA[Pos - 1] = lca(W[Pos - 1], W[Pos]);
                if(Pos < M) LCA[Pos] = lca(W[Pos], W[Pos + 1]);
            } else {
                int L, R, v;
                pair <int, int> Ans = {-1, -1};
                cin >> L >> R >> v;
                for(int i = L; i < R; i++){
                    if(LCA[i] == v){
                        Ans.first = i, Ans.second = i + 1;
                        break;
                    } if(W[i] == v){
                        Ans.first = i, Ans.second = i;
                        break;
                    }
                }
                if(W[R] == v) Ans.first = R, Ans.second = R;
                cout << Ans.first << ' ' << Ans.second << '\n';
            }
        }
    }

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