Submission #1159695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159695		jus_teng	September (APIO24_september)	C++20	Compilation error	0 ms	0 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
*/

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

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

    long long days = 0;

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

        vector<long long> todayFallen;
        
        while (!q.empty()){
            
            long long node = q.front();
            q.pop();
            todayFallen.push_back(node);

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

        set<long long> todaySet(todayFallen.begin(), todayFallen.end());

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

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

    return days == k;
}

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

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

    return ans;
}

int main(){
    
    long long t;
    scanf("%lld", &t);

    for (int i = 0; i < t; i++){
        
        scanf("%lld %lld", &n, &m);

        vector<long long> f(n);
        vector<vector<long long>> s(m, vector<long long>(n - 1));

        for (long long i = 1; i < n; i++){
            
            scanf("%lld", &f[i]);
        }

        for (long long i = 0; i < m; i++){
            
            for (long long j = 0; j < n - 1; j++){
                
                scanf("%lld", &s[i][j]);
            }
        }

        adj.assign(n, vector<long long>());
        inDegree.assign(n, 0);

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

        printf("%lld\n", binSearch(s));
    }

    return 0;
}

Compilation message (stderr)

september.cpp: In function 'int main()':
september.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%lld", &t);
      |     ~~~~~^~~~~~~~~~~~
september.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%lld %lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
september.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |             scanf("%lld", &f[i]);
      |             ~~~~~^~~~~~~~~~~~~~~
september.cpp:130:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 scanf("%lld", &s[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccdFAjnR.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3rOljH.o:september.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccdFAjnR.o: in function `mtbpdhr2zxjo1o4i9oreohsbuzzl4s6u::taskcase()':
grader.cpp:(.text+0x50d): undefined reference to `solve(int, int, std::vector<int, std::allocator<int> >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status