Submission #1201515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201515		AMel0n	September (APIO24_september)	C++17	64 / 100	860 ms	21516 KiB

september

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first 
// #define S second

#include "september.h"


int solve(int N, int M, vector<int> P, vector<vector<int>> S) {
    vector<vector<int>> C(N);
    for(int i = 1; i < N; i++) C[P[i]].push_back(i);

    unordered_set<int> hL; // hanging leaves
    map<int, pair<bool,int>> done; // leaf is seen by worker 0, # times leaf is seen
    set<pair<int,int>> check; // checking if every leaf has been seen the same amnt of times (by all the workers)

    int K = 0;
    FOR(i, S[0].size()) {
        int cur = S[0][i];

        done[cur].first = true;
        if (hL.find(cur) != hL.end()) hL.erase(hL.find(cur));

        C[P[cur]].erase(find(all(C[P[cur]]), (cur))); 
        for(auto c: C[cur]) {
            if (!done[c].first) {
                hL.insert(c);
            }
        }

        FOR(j, M) {
            int leaf = S[j][i];
            if (done[leaf].second == 0) {
                check.insert({1, leaf});
                done[leaf].second++;
            }
            else {
                check.erase(check.find({done[leaf].second, leaf}));
                check.insert({done[leaf].second+1, leaf});
                done[leaf].second++;
            }
        }
        
        if (hL.empty() && check.begin()->first == prev(check.end())->first) K++;
    }
    return K;
}

// signed main() {
//     cin.tie(0); ios::sync_with_stdio(false);

// }

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