Submission #1157142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157142		LolkasMeep	September (APIO24_september)	C++20	45 / 100	306 ms	25988 KiB

september

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

typedef long long int ll;

int dsuParents[100005];
int dsuSizes[100005];
bool visited[100005];
    
int getParent(int node){
    // cout << "[pop]" << node << '\n';
    if(dsuParents[node] == -1 || dsuParents[node] == node) return node;
    dsuParents[node] = getParent(dsuParents[node]);
    return dsuParents[node];
}

void createNode(int node){
    dsuParents[node] = node;
    dsuSizes[node] = 1;
}

bool merge(int a, int b){
    int pA = getParent(a);
    int pB = getParent(b);
    if (pA == pB) return false;
    if(dsuSizes[pA] > dsuSizes[pB]) swap(pA, pB);
    dsuParents[pA] = pB;
    dsuSizes[pB] += dsuSizes[pA];
    return true;
}

int solveM(int N, vector<int> &F, vector<int> S, vector<unordered_set<int>> &adjList){
    for(int i=0;i<100005;i++){
        dsuParents[i]=-1;
        dsuSizes[i]=0;
        visited[i]=false;
    }

    visited[0] = true;

    int components = 1;
    int counts = 0;
    for(int i = S.size() - 1; i >= 0; i--){
        components++;

        // cout << "Creaiting: " << S[i] << '\n';
        createNode(S[i]);

        for(int node : adjList[S[i]]){
            if(visited[node] && merge(S[i], node)){
                components--;
                // cout << "Joining: " << node << " " << S[i] << '\n';
            }
        
        }

        // cout << "Components: " << components << '\n';

        visited[S[i]] = true;
        if(components == 1) counts++;
    }



    return counts;
    
}


int solve(int N, int M, vector<int> F,vector<vector<int>> S){
    int minSize = 99999999;
    vector<unordered_set<int>> adjList(N);
    for(int i = 1; i < N; i++){
        adjList[i].insert(F[i]);
        adjList[F[i]].insert(i);
    }

    for(int j = 0; j < M; j++){
        // cout << "tooot\n";
        minSize = min(minSize, solveM(N, F, S[j], adjList));
        // cout << "Test" << minSize << '\n';
    }
    return minSize;
}

// int main(){

//     cout << "poop\n";

//     cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';

//     return 0;
// }

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