Submission #1203703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203703		yonatanl	September (APIO24_september)	C++20	0 / 100	1096 ms	1114112 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>;

vvll tree;

void dfs(ll node, ll papa, vll& dp, map<ll, ll>& idx) {
	for (auto& nei : tree[node]) {
		if (nei == papa) continue;
		dfs(nei, node, dp, idx);
		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.resize(n);
	rep(i, 1, n) {
		tree[i].push_back(F[i]);
		tree[F[i]].push_back(i);
	}
	ll ans = 0;
	rep(i, 0, m) {
		map<ll, ll> mp; // idx[x] = the index of x in the current array
		vll dp(n);
		//dp[Sn - 1] = n - 1;
		rep(j, 0, n - 1) {
			mp[S[i][j]] = j;
			dp[S[i][j]] = j;
		}
		dfs(0, -1, dp, mp);
		//rep(j, 0, n) cout << dp[j] << ' ';
		//cout << endl;
		vll arr(n - 1);
		rep(j, 0, n - 1) {
			arr[j] = dp[S[i][j]];
		}
		//rep(j, 0, n - 1) cout << arr[j] << " ";
		//cout << endl;
		ll curEnd = arr[0];
		rep(j, 0, n - 1) {
			upmax(curEnd, arr[j]);
			if (j == curEnd) {
				ans++;
			}
		}
	}
	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
*/

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