Submission #1158847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158847		jus_teng	9월 (APIO24_september)	C++20	Compilation error	0 ms	0 KiB

september

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

/*Kahn's algorithm (topological sorting) adapted from https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/*/

long long kahnAlgo(long long n, long long m, vector<long long> f, vector<vector<long long>> s){
    vector<vector<long long>> tree(n); 
    vector<long long> indegree(n, 0);

    for (long long i = 1; i < n; i++){
        
        tree[f[i]].push_back(i);
        indegree[i]++;
    }

    queue<long long> q;
    
    for (long long i = 1; i < n; i++){
        
        if (indegree[i] == 0){
            
            q.push(i);
        }
    }

    vector<long long> leafOrder; 
    
    while (!q.empty()){
        
        long long node = q.front();
        q.pop();
        leafOrder.push_back(node);
        
        long long parent = f[node];
        
        if (--indegree[parent] == 0 && parent != 0){
            
            q.push(parent);
        }
    }

    long long maxK = 1;  
    
    for (long long i = 0; i < m; i++){
        
        unordered_map<long long, long long> day;
        long long currentDay = 1;
        
        for (long long leaf : s[i]){
            
            if (day.count(leaf) && day[leaf] != currentDay){
                
                return 1;
            }
            
            day[leaf] = currentDay;
            
            if (leafOrder.back() == leaf){
                
                leafOrder.pop_back();
                currentDay++;
            }
        }
        
        maxK = max(maxK, currentDay);
    }
    
    return maxK;
}

int main(){
    
    long long t, n, m;
    scanf("%lld", &t);
    
    for (int i = 0; i < t; i++){
        scanf("%lld %lld", &n, &m);
        vector<long long> f(n);
        f[0] = -1; 
        
        for (long long i = 1; i < n; i++){
            
            scanf("%lld", &f[i]);
        }

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

        printf("%lld\n", kahnAlgo(n, m, f, s));
    }
    
    return 0;
}

Compilation message (stderr)

september.cpp: In function 'int main()':
september.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%lld", &t);
      |     ~~~~~^~~~~~~~~~~~
september.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%lld %lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
september.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%lld", &f[i]);
      |             ~~~~~^~~~~~~~~~~~~~~
september.cpp:92:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |                 scanf("%lld", &s[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccZFEWl5.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccxr8uVn.o:september.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccZFEWl5.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