Submission #991513

#	Time	Username	Problem	Language	Result	Execution time	Memory
991513		Muaath_5	September (APIO24_september)	C++17	100 / 100	588 ms	16092 KiB

september

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 1e5+1;

int tree[4*N];

void update(int idx, int l = 0, int r = N-1, int node=1) {
	if (l == r) {
		tree[node] = 1;
		return;
	}
	
	const int mid = (l+r)/2;
	if (idx <= mid)
		update(idx, l, mid, node*2);
	else
		update(idx, mid+1, r, node*2+1);
	
	tree[node] = tree[node*2] + tree[node*2+1];
}
int range_sum(int ql, int qr, int l = 0, int r = N-1, int node=1) {
	if (ql <= l && r <= qr) return tree[node];
	if (l > qr || r < ql) return 0;
	const int mid = (l+r)/2;
	return range_sum(ql, qr, l, mid, node*2) + range_sum(ql, qr, mid+1, r, node*2+1);
}

vector<int> adj[N];
int ttm, dt[N], ft[N];

void dfs(int node) {
	dt[node] = ttm++;
	for (int ch : adj[node]) {
		dfs(ch);
	}
	ft[node] = ttm-1;
}

int ismad(int node) {
	return range_sum(dt[node], ft[node]) < ft[node] - dt[node] + 1;
}

int solve(int n, int m, std::vector<int> P, std::vector<std::vector<int>> S) {
	memset(tree, 0, sizeof tree);
	ttm = 0;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}	
	for (int i = 1; i < n; i++) {
		adj[P[i]].push_back(i);
	}
	dfs(0);
	int days = 0;
	int idx = 0;
	int madcnt = 0;
	while (idx < n-1) {
		do {
			for (int i = 0; i < m; i++) {
				// append S[i][idx] if not appended
				if (range_sum(dt[S[i][idx]], dt[S[i][idx]]) == 0) {
					update(dt[S[i][idx]]);
					int node = S[i][idx];
					if (ismad(node)) {
						madcnt++;
					} else {
						while (node != 0 && !ismad(P[node])) {
							madcnt--;
							node = P[node];
						}	
					}
				}
				
			}
			idx++;
			
		}
		while (idx < n-1 && (range_sum(0, n) != idx || madcnt));
		days++;
	}
	return days;
}

#ifdef MUAATH_5
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cout << solve(3, 1, {-1, 0, 0}, {{1, 2}}) << '\n';
	cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';
	cout << solve(7, 1, {-1, 0, 0, 1, 1, 3, 3}, {{3, 1, 4, 6, 2}}) << '\n';
}
#endif

• 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