Submission #343512

#	Time	Username	Problem	Language	Result	Execution time	Memory
343512		koketsu	Birthday gift (IZhO18_treearray)	C++14	30 / 100	4069 ms	3052 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);
#define int LL

using namespace std;

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

vector <int> g[Mxn];

int F[Mxn], A[Mxn];

void Dfs(int v, int p){
    F[v] = p;
    for(auto i : g[v]){
        if(i == p) continue;
        Dfs(i, v);
    }
}

void Check(int v, int B, bool &Ans, vector <bool> &Used){
    if(v == -1) return;
    if(Used[v]){
        if(v == B) Ans = true;
        return;
    }
    Used[v] = true;
    Check(F[v], B, Ans, Used);
}

signed main(){
    Kultivator;
    int N, M, Q;
    cin >> N >> M >> Q;
    for(int i = 1, L, R; i < N; i++){
        cin >> L >> R;
        g[L].pb(R);
        g[R].pb(L);
    }
    Dfs(1, -1);
    for(int i = 1; i <= M; i++){
        cin >> A[i];
    }
    while(Q--){
        int T;
        cin >> T;
        if(T == 1){
            int Pos, Id;
            cin >> Pos >> Id;
            A[Pos] = Id;
        } else {
            int L, R, V;
            pair <int, int> Ans = {-1, -1};
            cin >> L >> R >> V;
            for(int i = L; i < R; i++){
                if(A[i] == V){
                    Ans.first = Ans.second = i;
                    break;
                }
                bool W = false;
                vector <bool> Used(N + 1, false);
                Check(A[i], V, W, Used);
                Check(A[i + 1], V, W, Used);
                if(W){
                    Ans.first = i;
                    Ans.second = i + 1;
                    break;
                }
            }
            if(A[R] == V) Ans.first = Ans.second = R;
            cout << Ans.first << ' ' << Ans.second << '\n';
        }
    }
}

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