Submission #1000763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000763		vuavisao	September (APIO24_september)	C++17	64 / 100	1060 ms	32704 KiB

september

#include "september.h"
 
#include <vector>

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

using ll = long long;
 
const int N = 100'000 + 10;
const int INF = 1'000'000'000;

struct FenWick {
	int n_node = 0;
	int tree[N];

	void resize(int n) { n_node = n; for (int i = 0; i <= n_node; ++ i) tree[i] = 0; }
	FenWick() {};
	FenWick(int n) { this->resize(n); };

	void Update(int idx, int val) {
		for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] += val;
		return;
	}

	int Query(int idx) {
		int res = 0;
		for ( ; idx > 0; idx -= (idx & - idx)) res += tree[idx];
		return res;
	}

	int Sum_to(int l, int r) {
		if (l > r) return 0;
		return Query(r) - Query(l - 1);
	}

	int kth(int val) {
		int res = 0, s = 0;
		for (int mask = 30; mask >= 0; -- mask) {
			int nxt = res | (1 << mask);
			if (nxt < n_node && s + tree[nxt] < val) {
				res = nxt;
				s += tree[nxt];
			}
		}
		++ res; return res;
	}
};

int n, m;
int parent[N];
vector<int> g[N];
int perRem[10][N];

int need[10][N];

namespace Order {
	struct que {
		int idx;
		int l, r, mid;
		que() {};
		que(int _idx, int _l, int _r) : idx(_idx), l(_l), r(_r) {};
		
		void reCalculate() {
			mid = (l + r) >> 1;
		}

		bool operator<(const que& other) const {
			return this->mid < other.mid;
		}
	};

	int cnt;
	int in[N], out[N];

	FenWick bit;

	void dfs(int u) {
		in[u] = ++ cnt;
		for (const auto& v : g[u]) dfs(v);
		out[u] = cnt;
	}
	
	void solve(int perRem[], int res[]) {
		cnt = 0;
		dfs(1);
		vector<que> qq;
		for (int i = 1; i < n; ++ i) {
			qq.push_back(que(i, 1, n - 1));
			qq.back().reCalculate();
			res[i] = n - 1;
		}
		bit.resize(n);
		while (!qq.empty()) {
			vector<que> newQQ;
			sort(qq.begin(), qq.end());
			int last = 1;
			for (auto& [idx, l, r, mid] : qq) {
				while (last <= mid) {
					const auto& u = perRem[last];
					bit.Update(in[u], 1);
					++ last;
				}
				int u = perRem[idx];
				
				if (bit.Sum_to(in[u], out[u]) == out[u] - in[u] + 1) {
					res[idx] = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
				if (l <= r) {
					newQQ.push_back(que(idx, l, r));
					newQQ.back().reCalculate();
				}
			}
			for (int i = last - 1; i >= 1; -- i) bit.Update(in[perRem[i]], -1);
			qq = newQQ;
		}
	}
}

namespace One {
	bool check() {
		return (m == 1);
	}

	struct SegTree {
		struct Node {
			int val = -INF;
			Node() {};
			Node(int _val) : val(_val) {};
			Node operator + (const Node& other) const {
				Node res;
				res.val = max(this->val, other.val);
				return res;
			}
		};
	
		int n_node = 0;
		Node tree[N << 2];
	
		void resize(int _n) { n_node = _n; for (int i = 0; i <= (n_node << 2); ++ i) tree[i] = Node(); };
		SegTree() {};
		SegTree(int _n) { this->resize(_n); };
	
		void update(int node, int l, int r, int idx, int val) {
			if (l == r) {
				tree[node].val = val;
				return;
			}
			int mid = (l + r) >> 1;
			if (idx <= mid) update(node << 1, l, mid, idx, val);
			else update(node << 1 | 1, mid + 1, r, idx, val);
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	
		void Update(int idx, int val) {
			return update(1, 1, n_node, idx, val);
		}
	
		Node query(int node, int l, int r, int L, int R) {
			if (L <= l && r <= R) return tree[node]; 
			int mid = (l + r) >> 1;
			if (R <= mid) return query(node << 1, l, mid, L, R);
			if (L > mid) return query(node << 1 | 1, mid + 1, r, L, R);
			return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
		}
	
		Node Query(int l, int r) {
			return query(1, 1, n_node, l, r);
		}
	};

	vector<int> open[N];
	int dp[N];

	FenWick bit;
	SegTree st;

	int solve() {
		for (int i = 0; i <= n + 1; ++ i) {
			vector<int>().swap(open[i]);
			dp[i] = -INF;
		}
		for (int i = 1; i < n; ++ i) {
			open[need[1][i]].push_back(i);
		}
		dp[0] = 0;
		bit.resize(n);
		for (int i = 1; i < n; ++ i) bit.Update(i, 1);

		st.resize(n);
		for (int i = 1; i < n; ++ i) {
			for (const auto& idx : open[i]) bit.Update(idx, -1);
			st.Update(i, dp[i - 1]);
			int cnt = bit.Query(i);
			int last = bit.kth(cnt) + (cnt != 0);
			// cout << cnt << ' ' << last << '\n';
			if (last <= i) {
				dp[i] = st.Query(last, i).val + 1;
			}
		}
		return dp[n - 1];
	}
}

namespace Brute_force {
	bool check() {
		return (n <= 1'000);
	}

	unsigned seed = chrono::system_clock::now().time_since_epoch().count();
	mt19937_64 rng(seed); 

	ll Rand(ll a, ll b = 1ll * INF * INF) {
		return a + rng() % (b - a + 1);
	}

	bool can[1'010][1'010];
	ll base[N];
	ll Hash[10][N];

	vector<int> open[N];

	int exist[N];
	int dp[N];

	int solve() {
		srand(time(nullptr));
		for (int i = 0; i <= n + 1; ++ i) {
			dp[i] = -INF;
			exist[i] = 0;
			vector<int>().swap(open[i]);
		}
		for (int i = 0; i <= n + 1; ++ i) {
			for (int j = 0; j <= n + 1; ++ j) {
				can[i][j] = false;
			}
		}
		for (int i = 1; i <= n; ++ i) base[i] = Rand(1);
		for (int i = 1; i <= m; ++ i) {
			for (int j = 1; j < n; ++ j) {
				Hash[i][j] = base[perRem[i][j]];
				open[need[i][j]].push_back(j);
			}
		}
		for (int i = 1; i < n; ++ i) {
			ll xorHash[6];
			memset(xorHash, 0, sizeof(xorHash));
			for (int j = i; j < n; ++ j) {
				for (int k = 1; k <= m; ++ k) {
					xorHash[k] ^= Hash[k][j];
				}
				if (*min_element(xorHash + 1, xorHash + 1 + m) == *max_element(xorHash + 1, xorHash + 1 + m)) {
					can[i][j] = true;
				}
			}
		}
		dp[0] = 0;
		for (int i = 1; i < n; ++ i) {
			for (const auto& idx : open[i]) ++ exist[idx];
			for (int j = i; j >= 1; -- j) {
				if (exist[j] < m) break;
				if (can[j][i]) {
					// cout << j << ' ' << i << ' ' << dp[i] << ' ' << dp[j - 1] << '\n';
					dp[i] = max(dp[i], dp[j - 1] + 1);
				}
			}
		}
		return dp[n - 1];
	}
}
 
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n = N; m = M;
	for (int i = 0; i <= n + 1; ++ i) g[i].clear();
	for (int v = 2; v <= n; ++ v) {
		int u = F[v - 1] + 1;
		g[u].push_back(v);
		parent[v] = u;
		// cerr << u << ' ' << v << '\n';
	}
	for (int i = 0; i < m; ++ i) {
		for (int j = 0; j < n - 1; ++ j) {
			perRem[i + 1][j + 1] = S[i][j] + 1;
			// cerr << i + 1 << ' ' << j + 1 << ' ' << perRem[i + 1][j + 1] << ' ' << S[i][j] << '\n';
		}
	}

	for (int i = 1; i <= m; ++ i) {
		Order::solve(perRem[i], need[i]);
		// for (int j = 1; j <= n; ++ j) cout << need[i][j] << ' ';
	}
 
	if (One::check()) {
		return One::solve();
	}
	if (Brute_force::check()) {
		return Brute_force::solve();
	}
	return 0;
}

• 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: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16