제출 #1123597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123597		vladilius	9월 (APIO24_september)	C++20	100 / 100	753 ms	28120 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 = 2; 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];
            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]++];
                start(x);
            }
        }
    };
    
    int out = 0;
    for (int i = 0; i < n - 1; i++){
        int x = s[0][i];
        if (st.find(tin[x]) == st.end()) continue;
        start(x);
        out++;
    }
    
    return out;
}

• 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