Submission #1158029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158029		cleversquid	September (APIO24_september)	C++17	0 / 100	1 ms	396 KiB

september

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


using namespace std;

/*
N = Number of Nodes
M = Number of Volunteers
F = Represents the Graph (F[i] = parent of node i)
S = M arrays, each one representing the Volunteer's record
*/


/*When you wake up tomorrow:
Insert printsets for debugging and check final iteration
*/

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


void dfs(int start, vector<bool> &visited, vector<vector<int> > &children, int &ctr){
    //adjacency list not needed because children is the adjacency list LOL
    if(visited[start] == true){
        return;
    }

    visited[start] = true;

    for(int neighbours: children[start]){
        if(!visited[neighbours]){
            children[start].push_back(neighbours);
            //keep track of number of 
            ctr++;
            dfs(neighbours, visited, children, ctr);
        }
    }
}


//each item in the vector represents the NUMBER OF CHILDREN THAT NODE HAS



int solve(int N, int M, vector<int> F, vector<vector<int> > S){
    //cout << F[0] << " " << S[0][0] << "\n";
    
    /*Generate adjacency list*/
    
    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;
    int ctr = 0;

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

    for(int i = 0; i<N-1; i++){  
        //cout << "ITERATION " << i << ": \n"; 

        for(int j = 0; j<M; j++){
            //cout << "\tChecking element " << S[j][i] << "..\n";
            //cout << "---\n";
            anticipated.insert(S[j][i]);
            /*cout << "\n---\tCOUNTERS LIST: \n";
            for(int i =  0; i<N; i++){
                cout << counters[i] << " ";
            }
            cout << "\n---\tVISITED LIST: \n";
            for(int i =  0; i<N; i++){
                cout << visited[i] << " ";
            }*/
            
            
            //cout << "\t* ADDING: " << S[j][i] << "\n";
            //printSet(anticipated);

            int element = S[j][i];

            //
            if(visited[element] == false){
                //cout << "\t1. This element has not been visited yet, but has already been MARKED OTHERWISE with +1\n";
                visited[element] = true;
                counters[element]++;

                dfs(element, visited, children, ctr);

                //i forgot DFS was a thing and tried doing an iterative thing :penchickdead:
                /*for(int k = 0; k<children[element].size(); k++){

                    //children[element][k] = within a specific element, kth index across iteration
                    int child = children[element][k];
                    anticipated.insert(child);

                    if(visited[child] == false){

                        //make sure the 
                        cout << "\t2." << k+1 << " The child, " << children[element][k] << ", hasn't been visited and has already been MARKED OTHERWISE with +1.\n";
                        visited[child] = true;
                    }
                    else{
                        cout << "\t2." << k+1 << " The child, " << children[element][k] << ", has been visited already and is ignored.\n";
                    }
                }*/
            }
            else{
                counters[element]++;
            }

            if(counters[element] >= M){
                //cout << "\t!!!. ELEMENT HAS REACHED MAX COUNT, TO BE ERASED IN SET...\n";
                anticipated.erase(element);
            }
        }   



        if(anticipated.size() == 0){
            //cout << "\t!!!. A DAY HAS BEEN COMPLETED, RESETTING...\n";
            answer++;

            anticipated.clear();
            counters.assign(N+5, false);
        }
    }



    //anticipate and un-ancitipate

    //perform DFS for children

    return answer;
}




/*int main(){
    //delete when done
    int N, M;
    cin >> N >> M;
    
    vector<int> F;
    vector<vector<int> > S(M, vector<int>(N-1));

    for(int i = 0; i<=N-1; i++){
        int x;
        cin >> x;
        F.push_back(x);
    }

    for(int i = 0; i<M; i++){
        for(int j = 0; j<N-1; j++){
            int x;
            cin >> x;
            S[i][j] = x;
        }
    }

    cout << "\n";

    for(int i = 0; i<M; i++){
        for(int j = 0; j<N-1; j++){
            cout << S[i][j] << " ";
        }
        cout << "\n";
    }





    cout << solve(N, M, F, 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