제출 #1159722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159722		jus_teng	September (APIO24_september)	C++20	0 / 100	0 ms	324 KiB

september

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

/*Topological BFS + Binary Search approach

Topological BFS adapted from https://cp-algorithms.com/graph/breadth-first-search.html and https://cp-algorithms.com/graph/topological-sort.html
Modifications:
- Topological DFS changed to topological BFS
- Queue and in-degree array instead of recursion
- Zero in-degree nodes processed first

Binary Search adapted from https://cp-algorithms.com/num_methods/binary_search.html
Modifications:
- Binary search is used for max possible K days instead of sorted array
- Each check does leaf removal through Topological BFS*/

int n, m;
vector<vector<int>> adj;
vector<int> inDegree;

bool topBFS(int k, vector<vector<int>>& s){
    
    queue<int> q;
    vector<int> remainingInDegree = inDegree;
    
    for (int i = 0; i < n; i++){
        
        if (remainingInDegree[i] == 0){
            
            q.push(i);
        }
    }

    int days = 0;
    int processed = 0; 

    for (int day = 0; day < k; day++){
        
        if (q.empty()){
            
            return false; 
        }

        vector<int> todayFallen;
        int size = q.size();

        while (size--){
            
            int node = q.front();
            q.pop();
            todayFallen.push_back(node);
            processed++;

            for (int parent : adj[node]){
                
                remainingInDegree[parent]--;
                
                if (remainingInDegree[parent] == 0){
                    
                    q.push(parent);
                }
            }
        }

        set<int> todaySet(todayFallen.begin(), todayFallen.end());
        
        for (int v = 0; v < m; v++){
            
            int start = (day == 0) ? 0 : (day * (n - 1) / k);
            int end = min((day + 1) * (n - 1) / k, (int)s[v].size());

            for (int i = start; i < end; i++){
                
                if (todaySet.find(s[v][i]) == todaySet.end()){
                    
                    return false;
                }
            }
        }

        days++;
    }

    return (processed == n - 1);
}

int binSearch(vector<vector<int>>& s){
    
    int left = 1, right = n - 1, ans = 1;

    while (left <= right){
        
        int mid = (left + right) / 2;
        
        if (topBFS(mid, s)){
            
            ans = mid;
            left = mid + 1;
        } 
        
        else{
            
            right = mid - 1;
        }
    }

    return ans;
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S){
    
    n = N;
    m = M;
    adj.assign(n, vector<int>());
    inDegree.assign(n, 0);

    for (int i = 1; i < n; i++){
        
        int parent = F[i];
        adj[parent].push_back(i);
        inDegree[i]++;
    }

    return binSearch(S);
}

• 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