Submission #1204658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204658		yonatanl	September (APIO24_september)	C++20	100 / 100	389 ms	30972 KiB

september

#include "september.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

vvll tree;

void dfs(ll node, ll papa, vll& dp) {
	for (auto& nei : tree[node]) {
		if (nei == papa) continue;
		dfs(nei, node, dp);
		upmax(dp[node], dp[nei]);
		//upmax(dp[node], idx[nei]);
	}
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	ll n = N, m = M;
	tree.clear();
	tree.resize(n);
	rep(i, 1, n) {
		tree[i].push_back(F[i]);
		tree[F[i]].push_back(i);
	}
	int ans = 0;
	vvpll arr(m, vpll(n - 1));
	rep(i, 0, m) {
		vll dp(n);
		rep(j, 0, n - 1) {
			dp[S[i][j]] = j;
		}
		dfs(0, -1, dp);
		rep(j, 0, n - 1) {
			arr[i][j].first = dp[S[i][j]];
			arr[i][j].second = S[i][j];
		}
	}
	ll curEnd = 0;
	multiset<ll> s;
	map<ll, ll> cnt;
	rep(i, 0, m) {
		upmax(curEnd, arr[i][0].first);
		cnt[arr[i][0].second]++;
		s.insert(arr[i][0].second);
		if (cnt[arr[i][0].second] == m) {
			s.erase(arr[i][0].second); // Check if this erases all of the elements!!!
		}
	}
	if (curEnd == 0 && s.empty()) ans++;
	ll curPtr = 1;
	while (curPtr < n - 1) {
		rep(i, 0, m) {
			upmax(curEnd, arr[i][curPtr].first);
			cnt[arr[i][curPtr].second]++;
			s.insert(arr[i][curPtr].second);
			if (cnt[arr[i][curPtr].second] == m) {
				s.erase(arr[i][curPtr].second); // Check if this erases all of the elements!!!
			}
		}
		if (curPtr == curEnd && s.empty()) ans++;
		curPtr++;
	}
	return ans;
}


/*
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll N, M;
	cin >> N >> M;
	vector<int> F(N);
	F[0] = -1;
	vector<vector<int>> S(M, vector<int>(N - 1));
	rep(i, 1, N) cin >> F[i];
	rep(i, 0, M) {
		rep(j, 0, N - 1) {
			cin >> S[i][j];
		}
	}
	cout << solve(N, M, F, S) << endl;
}*/

/*
9 1
0 0 2 2 4 4 4 1
8 4 6 3 7 2 5 1

3 1
0 0
2 1

5 1
0 0 1 1
3 1 2 4

10 1
3 0 0 2 3 5 3 6 5
4 7 6 9 8 5 1 2 3
*/

• 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