제출 #857578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857578		ymjoo12	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	104 ms	28200 KiB

minmaxtree

#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <vector>
using namespace std;
using pii = pair<int,int>;

const int N_MAX = 7e4, L_LMT = 17, INF = 1e9+1;
const pii DFLT = {0,INF};
int N, K, P[N_MAX+2][L_LMT+2], L[N_MAX+2], C[N_MAX+2], H[N_MAX+2], R[N_MAX+2];
pii A[N_MAX+2];
vector<int> edges[N_MAX+2];

struct Segtree {
    int prnt, flv, cnt;
    vector<int> arr;
    vector<pii> tree;
    void build() {
        int tsize = 1<<(33-__builtin_clz(arr.size()));
        tree.resize(tsize,DFLT);
    }
    void add(int u) {
        arr.push_back(u);
        prnt = P[u][0];
        flv = L[u];
        ++cnt;
    }
    pii apply(int n, pii v=DFLT) {
        pii& nd = tree[n];
        return nd = {max(nd.first,v.first),min(nd.second,v.second)};
    }
    void prop(int n) {
        apply(n*2,tree[n]);
        apply(n*2+1,tree[n]);
    }
    void _update(int kl, int kr, pii v, int l=0, int r=-1, int n=1) {
        if (r < 0) r = cnt-1;
        if (kl > r || kr < l) return;
        if (kl <= l && kr >= r) apply(n,v);
        else {
            prop(n);
            int m = (l+r)/2;
            _update(kl,kr,v,l,m,n*2);
            _update(kl,kr,v,m+1,r,n*2+1);
        }
    }
    void update(bool q, int v, int kr, int kl=-1) {
        if (kl < 0) kl = flv;
        else kl++;
        _update(kl-flv, kr-flv, q ? pii({0,v}) : pii({v,INF}));
    }
    void bulkApply(int l=0, int r=-1, int n=1) {
        if (r < 0) r = cnt-1;
        if (l == r) A[arr[cnt-l-1]] = tree[n];
        else {
            prop(n);
            int m = (l+r)/2;
            bulkApply(l,m,n*2);
            bulkApply(m+1,r,n*2+1);
        }
    }
};
vector<Segtree> paths;
unordered_set<int> st;

int init(int u=1, int l=1) {
    int mxv = 0;
    L[u] = l;
    for (int v : edges[u]) {
        if (L[v]) continue;
        P[v][0] = u;
        for (int i = 1; P[v][i-1]; ++i)
            P[v][i] = P[P[v][i-1]][i-1];
        if (C[u]) paths.push_back(Segtree());
        if (C[mxv] < init(v,l+1)) mxv = v;
        C[u] += C[v];
    }
    H[u] = mxv ? H[mxv] : paths.size()-1;
    paths[H[u]].add(u);
    return ++C[u];
}

int getAnsc(int u, int n) {
    for (int i = 0; n; n >>= 1, ++i) {
        if (n&1) u = P[u][i];
    }
    return u;
}

int getLca(int a, int b) {
    if (L[a] > L[b]) swap(a,b);
    b = getAnsc(b,L[b]-L[a]);
    if (a == b) return a;
    int ans = a;
    for (int i = 32-__builtin_clz(L[a]); i >= 0; --i) {
        if (P[a][i] == P[b][i]) ans = P[a][i];
        else a = P[a][i], b = P[b][i];
    }
    return ans;
}

void update(bool q, int v, int x, int y, bool lca=0) {
    if (L[x] > L[y]) swap(x,y);
    if (!lca) {
        int lca = getLca(x,y);
        if (lca != x) update(q,v,lca,x,1);
        update(q,v,lca,y,1);
    } else {
        while (H[x] != H[y]) {
            paths[H[y]].update(q,v,L[y]);
            y = paths[H[y]].prnt;
        }
        paths[H[y]].update(q,v,L[y],L[x]);
    }
}

bool exist(int z) {
    return st.find(z) != st.end();
}

int solve(int u=1) {
    for (int v : edges[u]) {
        if (v == P[u][0]) continue;
        st.insert(R[v]=solve(v));
    }
    auto [m,M] = A[u];
    if (M == INF || exist(M)) return m;
    if (m == 0 || exist(m)) return M;
    if (P[u][0]) {
        auto [pm,pM] = A[P[u][0]];
        if (M == pM) return m;
        if (m == pm) return M;
    }
    return m;
}

int main() {
    cin.tie(0)->ios::sync_with_stdio(0);

    cin >> N;
    for (int n = 1, a, b; n < N; ++n) {
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    paths.push_back(Segtree());
    init();
    for (auto& p : paths) p.build();

    cin >> K;
    char q; int x, y, z;
    while (K--) {
        cin >> q >> x >> y >> z;
        update(q=='M',z,x,y);
    }
    for (auto& p : paths) p.bulkApply();

    solve();
    for (int n = 2; n <= N; ++n) {
        cout << n << " " << P[n][0] << " " << R[n] << "\n";
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42