Submission #1167804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167804		dion324	September (APIO24_september)	C++20	0 / 100	1 ms	324 KiB

september

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define all(x) (x).begin(), (x).end()

using ll = long long;
using namespace std;

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    vector<vector<int>> tree(N);
    vector<int> indegree(N, 0);

    for (int i = 1; i < N; i++) {
        tree[F[i]].push_back(i);
        indegree[i]++;
    }

    queue<int> q;
    for (int i = 1; i < N; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    unordered_map<int, int> volunteer_pos[M];
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N - 1; j++) {
            volunteer_pos[i][S[i][j]] = j;
        }
    }

    auto is_valid = [&](int days) {
        vector<int> order(N - 1, -1);
        queue<int> temp_q = q;
        int day = 0;

        while (!temp_q.empty() && day < days) {
            int size = temp_q.size();
            vector<int> today;

            while (size--) {
                int node = temp_q.front();
                temp_q.pop();
                today.push_back(node);
            }

            sort(all(today), [&](int a, int b) {
                int min_pos_a = N, min_pos_b = N;
                for (int i = 0; i < M; i++) {
                    min_pos_a = min(min_pos_a, volunteer_pos[i][a]);
                    min_pos_b = min(min_pos_b, volunteer_pos[i][b]);
                }
                return min_pos_a < min_pos_b;
            });

            for (int x : today) order[x] = day;

            for (int x : today) {
                int parent = F[x];
                indegree[parent]--;
                if (indegree[parent] == 0 && parent != 0) temp_q.push(parent);
            }
            day++;
        }

        for (int i = 0; i < M; i++) {
            for (int j = 1; j < N - 1; j++) {
                if (order[S[i][j]] < order[S[i][j - 1]]) return false;
            }
        }

        return true;
    };

    int lo = 1, hi = N - 1, ans = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (is_valid(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 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