Submission #881702

#	Time	Username	Problem	Language	Result	Execution time	Memory
881702		Alcabel	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	1316 ms	197976 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5, maxlog = 18, inf = 1e9;
int a[maxn];
vector<int> g[maxn];
int sz[maxn], level[maxn], centPar[maxn][maxlog];
int dist[maxn][maxlog], mx[maxn][maxlog], idxNxt[maxn][maxlog];
vector<int> toutList;

void dfsSz(int v, int p) {
    sz[v] = 1;
    for (const int& u : g[v]) {
        if (u != p && level[u] == -1) {
            dfsSz(u, v);
            sz[v] += sz[u];
        }
    }
    toutList.emplace_back(v);
}

void dfsCalc(int v, int p, int j) {
    int i = 0;
    for (const int& u : g[v]) {
        if (u != p && level[u] == -1) {
            dist[u][j] = dist[v][j] + 1;
            mx[u][j] = max(mx[v][j], a[u]);
            centPar[u][j] = centPar[v][j];
            if (p != -1) {
                idxNxt[u][j] = idxNxt[v][j];
            } else {
                idxNxt[u][j] = i;
            }
            dfsCalc(u, v, j);
        }
        ++i;
    }
}

void findCentroid(int v, int j) {
    toutList.clear();
    dfsSz(v, -1);
    for (const int& c : toutList) {
        if (2 * sz[c] >= sz[v]) {
            v = c;
            break;
        }
    }
    // cerr << "j: " << j << ", v: " << v << '\n';
    level[v] = j;
    dist[v][j] = 0;
    mx[v][j] = a[v];
    centPar[v][j] = v;
    dfsCalc(v, -1, j);
    for (const int& u : g[v]) {
        if (level[u] == -1) {
            findCentroid(u, j + 1);
        }
    }
}

struct SegTree {
    int n, N;
    vector<int> st;
    SegTree() {}
    SegTree(int _n) {
        n = _n;
        N = 1;
        while (N < n) {
            N <<= 1;
        }
        st.resize(2 * N, -inf);
    }
    void maxEq(int i, int x) {
        int v = N + i;
        st[v] = max(st[v], x);
        v >>= 1;
        while (v > 0) {
            st[v] = max(st[2 * v], st[2 * v + 1]);
            v >>= 1;
        }
    }
    int getMax(int l, int r) {
        int vl = N + l, vr = N + r;
        int res = -inf;
        while (vl < vr) {
            if (vl & 1) {
                res = max(res, st[vl]);
            }
            if ((vr ^ 1) & 1) {
                res = max(res, st[vr]);
            }
            vl = (vl + 1) >> 1;
            vr = (vr - 1) >> 1;
        }
        if (vl == vr) {
            res = max(res, st[vl]);
        }
        return res;
    }
    ~SegTree() {}
};

SegTree st[maxn];

void solve() {
    int n;
    cin >> n;
    vector<int> posOf(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
        posOf[a[i]] = i;
        level[i] = -1;
    }
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].emplace_back(u);
        g[u].emplace_back(v);
    }
    for (int v = 0; v < n; ++v) {
        st[v] = SegTree(g[v].size());
    }
    findCentroid(0, 0);
    vector<int> dp(n);
    set<tuple<int, int, int>> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && get<0>(*s.begin()) <= i) {
            int v = get<1>(*s.begin()), j = get<2>(*s.begin());
            s.erase(s.begin());
            st[centPar[v][j]].maxEq(idxNxt[v][j], dp[a[v]] + dist[v][j]);
        }
        int v = posOf[i];
        for (int j = level[v]; j >= 0; --j) {
            if (mx[v][j] <= i) {
                int u = centPar[v][j];
                int val;
                if (j < level[v]) {
                    val = max(st[u].getMax(0, idxNxt[v][j] - 1), st[u].getMax(idxNxt[v][j] + 1, (int)g[u].size() - 1));
                    val = max(val, dp[a[u]]);
                } else {
                    val = max(val, st[u].getMax(0, (int)g[u].size() - 1));
                }
                if (val != -inf) {
                    dp[i] = max(dp[i], val + dist[v][j]);
                }
            }
        }
        // cerr << "i: " << i << ", dp: " << dp[i] << '\n';
        for (int j = level[v] - 1; j >= 0; --j) {
            s.emplace(mx[v][j], v, j);
        }
    }
    cout << dp[n - 1] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:139:21: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |                 int val;
      |                     ^~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26