Submission #1159690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159690		ProtonDecay314	September (APIO24_september)	C++20	100 / 100	78 ms	9620 KiB

september

#include "september.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define pb push_back

vi invert(const vi& a) {
    int n = a.size();
    n++;
    vi inv(n, 0);

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

    return inv;
}

int solve(int N, int M, vi F, vvi S) {
	vvi sinv;
    for(int i = 0; i < M; i++) {
        sinv.pb(invert(S[i]));
    }

    vpi consts;

    // Constraints across entries
    for(int i = 1; i < N; i++) {
        int mn = N, mx = 0;

        for(int j = 0; j < M; j++) {
            mn = min(mn, sinv[j][i]);
            mx = max(mx, sinv[j][i]);
        }

        consts.pb({mn, mx});
    }

    // Tree constraints
    for(int i = 1; i < N; i++) {
        // i is cur node
        int par = F[i]; // par is parent
        // par must be to the right of i
        // otherwise we have a constraint

        if(par == 0) continue;

        for(int j = 0; j < M; j++) {
            if(sinv[j][par] < sinv[j][i]) consts.pb({sinv[j][par], sinv[j][i]});
        }
    }

    // Solving the constraints
    vi to_add(N - 1, 0);

    for(auto [in, out] : consts) {
        to_add[in]++;
        to_add[out]--;
    }

    int cursum = 0;

    int ans = 0;

    for(int i = 0; i < N - 1; i++) {
        cursum += to_add[i];

        // cerr << cursum << " ";

        if(cursum == 0) ans++;
    }
    // cerr << endl;
    
    return ans;
}

• 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: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16