Submission #1278489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278489		Bui_Quoc_Cuong	September (APIO24_september)	C++20	16 / 100	1096 ms	716 KiB

september

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

int n, m;
vector <int> g[maxn];
int s[10][maxn];
int far[10][maxn];
int pos[maxn];
int dp[maxn];
vector <int> sorted[10];

void dfs (int u, int p, int min_id, int type) {
    far[type][u] = min_id;
    for (int &v : g[u]) {
        dfs(v, u, min(min_id, pos[u]), type);
    }
}

void build (int id_ver) {
    for (int i = 0; i < n - 1; i++) pos[s[id_ver][i]] = i;
    pos[0] = 2e9;
    dfs(0, 0, 2e9, id_ver);
}

int solve (int N, int M, vector <int> F, vector <vector <int>> S) {
    n = N;
    m = M;
    for (int i = 0; i < n; i++) {
        int u = F[i];
        if (u == - 1) continue;
        g[u].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n - 1; j++) s[i][j] = S[i][j];
    }

    for (int i = 0; i < m; i++) {
        build(i);
    }

    auto check = [&] (int l, int r, int m) {
        for (int i = 0; i < m; i++) {
            sort(sorted[i].begin(), sorted[i].end());
        }
        for (int i = 1; i < m; i++) {
            if (sorted[i] != sorted[0]) return 0;
        }

        for (int i = 0; i < m; i++) {
            for (int j = l; j <= r; j++) {
                int u = s[i][j];
                if (far[i][u] < l) return 0;
            }
        }

        return 1;
    };

    for (int i = 0; i < n; i++) {
      g[i].clear();
      dp[i] = - 1;
    }

    dp[0] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sorted[j].clear();
        }
        for (int j = i; j > 0; j--) {
            for (int t = 0; t < m; t++) {
                sorted[t].push_back(s[t][j]);
            }
            if (check(j - 1, i - 1, m)) {
                dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
    }
    

    return dp[n - 1];
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16