제출 #1151251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151251		tapilyoca	9월 (APIO24_september)	C++20	0 / 100	1096 ms	18168 KiB

september

/***********************************************
* auth: tapilyoca                              *
* date: 02/16/2025 at 20:02:38                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;

/***********************************************/


void DFS(int curr, vector<bool> &vis, unordered_set<int> &wait, vector<vector<int>> adj){
    vis[curr] = 1;
    wait.insert(curr);
    if(adj[curr].size() == 0){
        return;
    }

    for(int c : adj[curr]){
        DFS(c, vis, wait, adj);
    }
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S){
    
    vector<vector<int>> kids(N+1);
    for(int i = 1; i < N; i++){
        kids[F[i]].push_back(i);
    }

    vector<bool> vis(N+1, 0);
    unordered_set<int> waiting;
    vector<int> freq(N,0);
    int ans = 0;

    for(int i = 0; i < N-1; i++){
        for(int j = 0; j < M; j++){
            int at = S[j][i];
            waiting.insert(at);
            freq[at]++;
            
            if(!vis[at]){
                // then we haven't touched this yet
                // so set all of the children to be visited 
                DFS(at,vis,waiting,kids);
            }

            vis[at] = 1;

            if(freq[at] == M){
                waiting.erase(at);
            }
        }

        if(waiting.size() == 0){
            ans++;
        }
    }

    return ans;
}

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t = 1;
//     // cin >> t;

//     int n, m;
//     cin >> n >> m;
//     vector<int> a(n,0);
//     for(int i = 0; i < n; i++){
//         cin >> a[i];
//     }

//     vector<vector<int>> b;
//     for(int i = 0; i < m; i++){
//         vector<int> c(n-1,0);
//         for(int j = 0; j < n-1; j++) cin >> c[j];
        
//         b.push_back(c);
//     }


//     while(t--){
//         // cerr << "here" << endl;
//         cout << solve(n, m, a, b) << endl;
//     }

//     return 0;
// }

• 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