Submission #1279019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279019		Bui_Quoc_Cuong	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	458 ms	99516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n;
int a[N];
vector <int> ke[N];
int par[N];

namespace sub1 {
    int dp[5005];
    int dist[5005][5005];

    void DFS (int u) {
        for (int &v : ke[u]) if (v != par[u]) {
            par[v] = u;
            DFS(v);
        }
    }

    int find_max (int root, int border, int lim) {   
        vector <int> vis(n + 2, 0);
        vis[root] = vis[border] = true;
        queue <int> que;
        int max_node = 0;
        que.push(root);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            if (a[u] > a[max_node]) max_node = u;
            vis[u] = true;  
            for (int &v : ke[u]) if (!vis[v] && a[v] < lim) {
                que.push(v);
            }
        }
        return max_node;
    }

    int find_max_son (int u, int p, int lim) {
        int max_son = u;
        for (int &v : ke[u]) {
            if (v == p || a[v] > lim) continue;
            int choke = find_max_son (v, u, lim);
            if (a[choke] > a[max_son]) max_son = choke;
        }
        return max_son;
    }

    int dfs (int u, int p) {   
        if (dp[u] != - 1) return dp[u];
        dp[u] = 0;

        vector <int> umax;
        int s0 = find_max (u, p, a[u]);

        if (s0 != - 1 && s0 != u) umax.push_back(s0);

        for (int &v : ke[u]) if (a[v] < a[u]) {
            int sv = find_max_son (v, u, a[u]);
            if (sv != u) umax.push_back(sv);
        }

        for (int &v : umax) {
            dp[u] = max(dp[u], dfs(v, u) + dist[u][v]);
        }

        return dp[u];
    }   

    void solve () {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = 2e9;
            }
            queue <int> que;
            dist[i][i] = 0;
            que.push(i);
            while (!que.empty()) {
                int u = que.front();
                que.pop();
                for (int &v : ke[u]) if (dist[i][v] > dist[i][u] + 1) {
                    dist[i][v] = dist[i][u] + 1;
                    que.push(v);
                }
            }
        }
        int root = max_element(a + 1, a + 1 + n) - a;
        DFS(root);
        memset(dp, - 1, sizeof dp);
        cout << dfs(root, 0);
    }
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        ke[u].push_back(v); ke[v].push_back(u);
    }

    if (n <= 5000) {
        sub1 :: solve();
    }
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "kieuoanh"

    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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