제출 #1152182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152182		elipsen	9월 (APIO24_september)	C++20	100 / 100	427 ms	33060 KiB

september

#include "september.h"
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#define v vector
#define u_m unordered_map
#define u_s unordered_set
#define q queue
using namespace std;

// Transform vector F into child lookup
u_m<int, u_s<int>> children;
// This shall be the record keeper for volunteers
u_m<int, int> recordCount;
// This shall be for tracking which leaves fall on the same day
q<int> dayFall;
// This shall be for optimization - tracks if we've seen a certain leaf
v<bool> tracked;

void accountFor(int leaf) {
	if (!(tracked[leaf])) {
		dayFall.push(leaf);
		tracked[leaf] = true;
		for (auto iter = children[leaf].begin(); iter != children[leaf].end(); iter++) {
			accountFor(*iter);
		}
	}
}

int solve(int N, int M, v<int> F, v<v<int>> S) {
	children.clear(); recordCount.clear();
	tracked.clear(); tracked.resize(N);
	int days = 0;
	for (int nodeInd = 1; nodeInd < N; nodeInd++) {
		children[F[nodeInd]].insert(nodeInd);
	}
	
	// Traverse the records
	for (int recordInd = 0; recordInd < N - 1; recordInd++) {
		// Take in new leaves
		for (int volunteerID = 0; volunteerID < M; volunteerID++) {
			int leaf = S[volunteerID][recordInd];
			accountFor(leaf);
			recordCount[leaf]++;
		}
		// Check the same-day list if any leaf's records have been satisfied
		if (!(dayFall.empty())) {
			int front = dayFall.front();
			while (recordCount[front] == M) {
				dayFall.pop();
				if (dayFall.empty()) break;
				front = dayFall.front();
			}
		}
		// The list being empty means everyone has been accepted for in that day
		if (dayFall.empty()) days++;
	}

	return days;
}

• 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