Submission #1123587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123587		vladilius	September (APIO24_september)	C++20	0 / 100	1 ms	580 KiB

september

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int solve(int n, int m, vector<int> p, vector<vector<int>> s){
    vector<int> g[n];
    for (int i = 1; i < n; i++){
        g[p[i]].pb(i);
    }
    vector<int> tin(n), tout(n), inv(n + 1);
    int timer = 0;
    function<void(int)> fill = [&](int v){
        tin[v] = ++timer;
        inv[tin[v]] = v;
        for (int i: g[v]){
            fill(i);
        }
        tout[v] = timer;
    };
    fill(0);
    
    set<int> st;
    for (int i = 1; i <= n; i++){
        st.insert(i);
    }
    
    vector<vector<int>> pos(n, vector<int>(m));
    for (int j = 0; j < m; j++){
        for (int i = 0; i < n - 1; i++){
            pos[s[j][i]][j] = i;
        }
    }
    
    vector<int> d(m);
    vector<bool> used(n);
    function<void(int)> start = [&](int v){
        vector<int> a(m);
        while (true){
            auto it = st.lower_bound(tin[v]);
            if (it == st.end() || (*it) > tout[v]) break;
            
            int x = inv[*it];
            used[x] = 1;
            st.erase(it);
            
            for (int i = 0; i < m; i++){
                a[i] = max(a[i], pos[x][i]);
            }
        }
        
        for (int j = 0; j < m; j++){
            while (d[j] <= a[j]){
                int x = s[j][d[j]];
                if (!used[x]){
                    start(x);
                }
                d[j]++;
            }
        }
    };
    
    int out = 0;
    for (int i = 0; i < n - 1; i++){
        int x = s[0][i];
        if (used[x]) continue;
        start(x);
        out++;
    }
    
    return out;
}

• 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