Submission #1095194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095194		RiverFlow	September (APIO24_september)	C++17	55 / 100	1091 ms	19512 KiB

september

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)1e5 + 9;
const int mod = (int)1e9 + 7;

int n, m;

int mx[N], a[5][N], L[N], R[N];

vector<int> g[N];

void dfs(int u, int p) {
    mx[u] = R[u];
    for(int v : g[u]) if (v != p) {
        dfs(v, u);
        mx[u] = max(mx[u], mx[v]);
    }
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    n = N, m = M;

    FOR(i, 0, n - 1) {
        g[i].clear();
        L[i] = n;
        R[i] = mx[i] = 0;
    }

    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n - 1; ++j)
            a[i][j] = S[i][j];
    }

    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n - 1; ++j) {
            maxi(R[a[i][j]], j);
            mini(L[a[i][j]], j);
        }
    }

    FOR(i, 1, n - 1) {
        g[F[i]].push_back(i);
    }

    dfs(0, -1);

    vector<int> dp(n + 1, -1);

    for(int i = 0; i < n - 1; ++i) {
        int r = 0;
        int e = n, b = 0;
        for(int j = i; j >= 0; --j) {
            r = max(r, mx[a[0][j]]);
            for(int t = 0; t < m; ++t) {
                mini(e, L[a[t][j]]);
                maxi(b, R[a[t][j]]);
            }
            if (r > i) break ;
            if (j <= e and b <= i and r <= i) {
                if (j == 0 or dp[j - 1] != -1) {
                    maxi(dp[i], (j > 0 ? dp[j - 1] : 0) + 1);
                }
            }
        }
    }

	return dp[n - 2];
}

#ifdef LOCAL
void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));

	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &F[i]));

	std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N - 1; ++j)
  			assert(1 == scanf("%d", &S[i][j]));

	printf("%d\n", solve(N, M, F, S));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
	int T;
	assert(1 == scanf("%d", &T));
	while(T--) taskcase();
	return 0;
}

#endif

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