Submission #1159634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159634		cleversquid	September (APIO24_september)	C++17	100 / 100	139 ms	10940 KiB

september

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;




void printSet(const unordered_set<int>& uset) {
    cout << "\tCurrent Unordered Set:\n\t";
    for (int elem : uset) {
        cout << elem << " ";
    }

    if(uset.size() == 0){
        cout << "empty :(";
    }
    cout << "\n";
}

void printVectorint(vector<int> &q) {
    cout << "\tCurrent Counters:\n\t";
    for (int elem : q) {
        cout << elem << " ";
    }
    cout << "\n";
}

void printVectorbool(vector<bool> &q) {
    cout << "\tCurrent Visited:\n\t";
    for (bool elem : q) {
        cout << elem << " ";
    }
    cout << "\n";
}


void dfs(int start, vector<bool> &visited, vector<vector<int> > &children, vector<int> &all_children){
    //adjacency list not needed because children is the adjacency list LOL

    //start is starting node
    //visited is the boolean of visited stuff. (use the same as the one in solve)
    //children is just an adjacency list
    //
   
   
   /* if(visited[start] == true){
        return;
    }*/

    visited[start] = true;

    for(int neighbours: children[start]){
        if(!visited[neighbours]){
            all_children.push_back(neighbours);
            dfs(neighbours, visited, children, all_children);
        }
    }
}





int solve(int N, int M, vector<int> F, vector<vector<int> > S){
    //cout << F[0] << " " << S[0][0] << "\n";
    
    //N is number of vertices
    //M is # of volunteers
    //F is children adjacency list
    //S is all records
    
    vector<vector<int> > children(N);

    for(int i = 1; i<N; i++){
        children[F[i]].push_back(i);
    }

    //PRINT OUT ALL CHILDREN

    int answer = 0;

    unordered_set<int> ant_set;
    vector<int> counters(N+5, 0);
    vector<bool> visited(N+5, false);

        for(int i = 0; i<N-1; i++){
            //i is the column
            //j is the row
    
            for(int j = 0; j<M; j++){
                int element = S[j][i];
                vector<int> all_children;
                all_children.clear();
                ant_set.insert(element);
                counters[element]++;
    
                if(visited[element] == false){
                    dfs(element, visited, children, all_children);

                    for(int k = 0; k<all_children.size(); k++){
                        ant_set.insert(all_children[k]);
                    }
                }

                visited[element] = true;
    
                if(counters[element] == M){
                    ant_set.erase(element);
                }
    
                /*printSet(ant_set);
                printVectorint(counters);
                printVectorbool(visited);*/
            }
    
            if(ant_set.size() == 0){
                answer++;
            }
            else{
    
            }
        }


    return answer;

}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16