Submission #1158856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158856		jus_teng	September (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(int n, int m, vector<int> f, vector<vector<int>> s){
  
    vector<vector<int>> tree(n);
    vector<int> indegree(n, 0);

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

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

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

    long long maxK = 1;
    
    for (int i = 0; i < m; i++){
      
        unordered_map<int, int> day;
        int currentDay = 1;
        
        for (int leaf : s[i]){
          
            if (day.count(leaf) && day[leaf] != currentDay){
              
                return 1;
            }
            day[leaf] = currentDay;
            
            if (!leafOrder.empty() && leafOrder.back() == leaf){
              
                leafOrder.pop_back();
                currentDay++;
            }
        }
        
        maxK = max(maxK, (long long)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:95:41: error: could not convert 'f' from 'vector<long long int>' to 'vector<int>'
   95 |         printf("%lld\n", kahnAlgo(n, m, f, s));
      |                                         ^
      |                                         |
      |                                         vector<long long int>
september.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld", &t);
      |     ~~~~~^~~~~~~~~~~~
september.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%lld %lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
september.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |             scanf("%lld", &f[i]);
      |             ~~~~~^~~~~~~~~~~~~~~
september.cpp:91:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |                 scanf("%lld", &s[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~