Submission #1151395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151395		jasonic	September (APIO24_september)	C++20	100 / 100	268 ms	15084 KiB

september

#include "september.h"
#include <bits/stdc++.h>

using namespace std;

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
    // we iteratively go through each 
    unordered_map<long long, vector<long long>> adjList;

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

    unordered_set<long long> seen;
    vector<long long> counts(N, 0);
    long long ans = 0;

    for(long long i = 0; i < N-1; i++) {
        for(long long j = 0; j < M; j++) {
            if(counts[S[j][i]] == 0) {
                // bfs to find which other nodes we have to track
                stack<long long> bfs;
                bfs.emplace(S[j][i]);
                while(bfs.size()) {
                    long long curr = bfs.top(); bfs.pop();
                    for(auto k : adjList[curr]) {
                        if(counts[k] == 0) {
                            bfs.emplace(k);
                        }
                    }
                    seen.emplace(curr);
                }
            }
            counts[S[j][i]]++;
            if(counts[S[j][i]] == M) {
                seen.erase(S[j][i]);
            }
        }
        if(seen.empty()) ans++;
    }

    return ans;
}

• 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