Submission #1158768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158768		BentoOreo	September (APIO24_september)	C++20	0 / 100	1 ms	328 KiB

september

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long long int, long long int>;
const int inf = numeric_limits<int>::max();
const ll INF = numeric_limits<ll>::max();
const char sp = ' ';
const char nl = '\n';

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S){
    vector<vector<int> > cutting_points(M);

    /*
    
    cuttingpoint i - Cut after i
    */
    //root is 0
    vector<vector<int> > adj(N); //children only
    unordered_set<int> leafs;
    vector<int> outdegree(N,0);
    for(int i = 0; i < N; i++){
        if(F[i] != -1){
            adj[F[i]].push_back(i);   
            outdegree[F[i]]++;
        }
    }
    for(int i = 0; i < N; i++){
        if(adj[i].size() == 0 && i != 0){
            leafs.insert(i);
        }
    }
    vector<unordered_set<int> > leafnodes(M, leafs);
    vector<bool> incompletes(M,false);
    vector<vector<int> > outdegreelist(M, outdegree);
    vector<vector<bool> > present(M, vector<bool>(N,true));
    vector<unordered_set<int> > tofind(M);
    vector<unordered_set<int> > segments(M); // tracks segments across all M

    int count = 0;
    for(int i = 0; i < N - 1; i++){
        for(int m = 0; m < M; m++){
            if(!incompletes[m]){
                if(leafnodes[m].count(S[m][i])){
                    outdegreelist[m][F[S[m][i]]]--;
                    leafnodes[m].erase(S[m][i]);
                    present[m][S[m][i]] = false;
                    if(outdegreelist[m][F[S[m][i]]] == 0){
                        leafnodes[m].insert(F[S[m][i]]);
                    }
                } else {
                    present[m][S[m][i]] = false;
                    for(int children: adj[S[m][i]]){
                        if(present[m][children]){
                            tofind[m].insert(children);
                        }
                    }
                    if(!tofind[m].empty()){
                        incompletes[m] = true;
                    }
                }
            } else {
                if(leafnodes[m].count(S[m][i])){
                    outdegreelist[m][F[S[m][i]]]--;
                    leafnodes[m].erase(S[m][i]);
                    present[m][S[m][i]] = false;
                    if(outdegreelist[m][F[S[m][i]]] == 0){
                        leafnodes[m].insert(F[S[m][i]]);
                    }
                    if(tofind[m].count(S[m][i])){
                        tofind[m].erase(S[m][i]);
                    }
                    if(tofind[m].empty()){
                        incompletes[m] = false;
                    }
                } else {
                    present[m][S[m][i]] = false;
                    for(int children: adj[S[m][i]]){
                        if(present[m][children]){
                            tofind[m].insert(children);
                        }
                    }
                }
            }
            segments[m].insert(S[m][i]);
        }
        bool okay = true;
        //if segments of all M are the same
        //if all not incomplete
        
        for(int m = 0; m < M; m++){
            if(incompletes[m]){
                okay = false;
                // cout << i << sp << "incomplete searchspace" << nl;
                break;
            }
            if(!tofind[m].empty()){
                okay = false;
                // cout << i << sp << "need to find something pa" << nl;
                break;
            }
        }
        for(int m = 1; m < M; m++){
            if(segments[0] != segments[m]){
                okay = false;
                // cout << i << sp << "unequal sets" << nl;
                break;
            }
        }
        if(okay){
            
            for(int m = 0; m < M; m++){
                segments[m].clear();
            }
            count++;
        }
    }
    return count;
}
// int main(){
//     cout << solve(5, 1, {-1, 0, 0, 1, 1}, {{4,3,1,2}}) << nl;
//     cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << nl;
//     cout << solve(3, 1, {-1, 0, 0}, {{1, 2}}) << nl;
//     cout << solve(7,1,{-1,0,0,1,1,2,2},{{2,6,5,3,1,4}}) << nl;
// }

• 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