Submission #782766

#	Time	Username	Problem	Language	Result	Execution time	Memory
782766		thimote75	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2068 ms	18764 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

idata height;
idata pos;

idata dp;
igrid roads;

int solve (int node, int parent, int depth) {
    if (dp[node] == -1) return 0;
    int mx = depth + dp[node];

    for (int next : roads[node]) if (next != parent)
        mx = max(mx, solve(next, node, depth + 1));

    return mx;
}

int main () {
    int N;
    cin >> N;

    height.resize(N);
    pos.resize(N);
    for (int i = 0; i < N; i ++) {
        cin >> height[i]; height[i] --;
        pos[height[i]] = i;
    }
    roads.resize(N);
    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;
        roads[a].push_back(b);
        roads[b].push_back(a);
    }
    dp.resize(N, -1);
    for (int i = 0; i < N; i ++) {
        dp[pos[i]] = 0;
        dp[pos[i]] = solve(pos[i], -1, 0);
    }

    cout << dp[pos[N - 1]] << endl;
}

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