oj.uz

답안 #651215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651215 2022-10-18T03:04:47 Z Astrayt Birthday gift (IZhO18_treearray) C++17
0 / 100
 9 ms 3412 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lc (p << 1)
#define rc ((p << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
array<int, 1 << 17> P, dep;
array<int, 1 << 20> S;
array<array<int, 18>, 1 << 17> A;
array<vector<int>, 1 << 17> T;
void DFS(int u, int pre, int d){
    dep[u] = d;
    for(int v : T[u]){
        if(v == pre) continue;
        A[v][0] = u;
        DFS(v, u, d + 1);
    }
}
void DABO(int n){
    for(int j = 1; j < 18; j++){
        for(int i = 1; i <= n; i++){
            A[i][j] = A[A[i][j - 1]][j - 1];
        }
    }
}
int LCA(int a, int b){
    if(!a || !b) return a? a : b;
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 17; i >= 0; i--){
        if(dep[A[b][i]] >= dep[a]) b = A[b][i];
    }
    if(a == b) return b;
    for(int i = 17; i >= 0; i--){
        if(A[a][i] != A[b][i]) a = A[a][i], b = A[b][i];
    }
    return A[a][0];
}
void pull(int p){
    S[p] = LCA(S[lc], S[rc]);
}
void update(int p, int l, int r, int c, int x){
    if(c < l && c > r) return;
    if(l == r){
        S[p] = x;
        return;
    }
    update(lc, l, mid, c, x);
    update(rc, mid + 1, r, c, x);
    pull(p);
}
int query(int p, int l, int r, int ql, int qr){
    if(qr < l || ql > r) return 0;
    if(ql <= l && qr >= r) return S[p];
    return LCA(query(lc, l, mid, ql, qr), query(rc, mid + 1, r, ql, qr));
}
int see(int l, int r, int m, int v){
    int p = l;
    for(int i = 1 << 17; i; i >>= 1){
        if(p + i <= r && dep[query(1, 1, m, l, p)] > dep[v]) p += i;
    }
    return p + 1;
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, m, q, u, v, a, t, l, r, p, can;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        T[u].pb(v), T[v].pb(u);
    }
    DFS(1, 0, 0);
    DABO(n);
    for(int i = 1; i <= m; i++){
        cin >> P[i];
        update(1, 1, m, i, P[i]);
    }
    while(q--){
        cin >> t >> l >> r;
        if(t == 1){
            P[l] = r;
            update(1, 1, m, l, r);
        }else{
            can = 0;
            cin >> v;
            for(int i = l; i <= r; i++){
                p = 0;
                for(int j = i; j <= r; j++){
                    p = LCA(p, P[j]);
                    if(p == v){
                        cout << i << " " << j << "\n";
                        can = 1;
                        break;
                    }
                }
            }
            if(!can) cout << "-1 -1\n";
        }
    }
    return 0;
}
/*
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
*/

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:65:24: warning: unused variable 'a' [-Wunused-variable]
   65 |     int n, m, q, u, v, a, t, l, r, p, can;
      |                        ^

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB n=5
2 Incorrect 9 ms 3412 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB n=5
2 Incorrect 9 ms 3412 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB n=5
2 Incorrect 9 ms 3412 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB n=5
2 Incorrect 9 ms 3412 KB Wrong range.
3 Halted 0 ms 0 KB -