Submission #1127468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127468		fzyzzz_z	September (APIO24_september)	C++20	100 / 100	187 ms	11800 KiB

september

#include <ios>
#include <iostream>
#include <vector>
using namespace std; 


// X X X X-X X X 
// X-X X X-X X X

int solve(int n, int m, vector<int> p, vector<vector<int>> s) {
    vector<vector<int>> g(n); 
    for (int i = 1; i < n; ++i) {
        g[p[i]].push_back(i);         
    }

    vector<int> good(n - 1, 1); 
    for (int t = 0; t < m; ++t) {
        vector<int> vis(n, 0), bad(n, 0);  
        for (int i = 0; i < n; ++i) bad[i] = g[i].size(); 
        int cnt = 0; 

        for (int i = 0; i < n - 1; ++i) {
            int x = s[t][i];

            vis[x] = 1; 
            if (bad[x] > 0) {
                cnt++; 
            } 
            if (p[x] != -1) {
                bad[p[x]]--; 
                if (bad[p[x]] == 0 && vis[p[x]]) {
                    cnt--; 
                }
            }

            good[i] &= (cnt == 0); 
        }
    }

    vector<int> has(n, 0); 
    int ans = 0, uni = 0; 
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            int x = s[j][i]; 
            if (has[x] == 0) {
                uni++; 
            }
            has[x]++; 
        }
        if (uni == i + 1 && good[i]) ans++; 
    }

    return ans; 
}


// int main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(0);

//     cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{4, 3, 2, 1}, {2, 3, 4, 1}});;
    

//     return 0;
// }

• 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