oj.uz

Submission #1000761

# Submission time Handle Problem Language Result Execution time Memory
1000761 2024-06-18T08:27:08 Z vuavisao September (APIO24_september) C++17
55 / 100
 1000 ms 26656 KB 
#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];

	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;
		}
		FenWick bit(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];

	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;
		FenWick bit(n);
		for (int i = 1; i < n; ++ i) bit.Update(i, 1);

		SegTree st(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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 3 ms 9560 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9564 KB Output is correct
12 Correct 3 ms 9768 KB Output is correct
13 Correct 3 ms 9308 KB Output is correct
14 Correct 3 ms 9388 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11356 KB Output is correct
2 Correct 12 ms 11276 KB Output is correct
3 Correct 13 ms 10996 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 12 ms 11356 KB Output is correct
9 Correct 12 ms 11276 KB Output is correct
10 Correct 13 ms 10996 KB Output is correct
11 Correct 13 ms 11136 KB Output is correct
12 Correct 13 ms 10844 KB Output is correct
13 Correct 12 ms 11272 KB Output is correct
14 Correct 12 ms 11304 KB Output is correct
15 Correct 13 ms 11256 KB Output is correct
16 Correct 12 ms 11372 KB Output is correct
17 Correct 13 ms 10872 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11356 KB Output is correct
2 Correct 12 ms 11276 KB Output is correct
3 Correct 13 ms 10996 KB Output is correct
4 Correct 15 ms 10584 KB Output is correct
5 Correct 15 ms 10844 KB Output is correct
6 Correct 15 ms 10844 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 3 ms 9560 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9564 KB Output is correct
12 Correct 3 ms 9768 KB Output is correct
13 Correct 3 ms 9308 KB Output is correct
14 Correct 3 ms 9388 KB Output is correct
15 Correct 12 ms 11356 KB Output is correct
16 Correct 12 ms 11276 KB Output is correct
17 Correct 13 ms 10996 KB Output is correct
18 Correct 13 ms 11136 KB Output is correct
19 Correct 13 ms 10844 KB Output is correct
20 Correct 12 ms 11272 KB Output is correct
21 Correct 12 ms 11304 KB Output is correct
22 Correct 13 ms 11256 KB Output is correct
23 Correct 12 ms 11372 KB Output is correct
24 Correct 13 ms 10872 KB Output is correct
25 Correct 15 ms 10584 KB Output is correct
26 Correct 15 ms 10844 KB Output is correct
27 Correct 15 ms 10844 KB Output is correct
28 Correct 16 ms 10840 KB Output is correct
29 Correct 15 ms 10844 KB Output is correct
30 Correct 15 ms 10816 KB Output is correct
31 Correct 15 ms 10844 KB Output is correct
32 Correct 16 ms 11020 KB Output is correct
33 Correct 16 ms 10588 KB Output is correct
34 Correct 15 ms 10844 KB Output is correct

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11356 KB Output is correct
2 Correct 12 ms 11276 KB Output is correct
3 Correct 13 ms 10996 KB Output is correct
4 Execution timed out 1066 ms 26656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 12 ms 11356 KB Output is correct
9 Correct 12 ms 11276 KB Output is correct
10 Correct 13 ms 10996 KB Output is correct
11 Correct 13 ms 11136 KB Output is correct
12 Correct 13 ms 10844 KB Output is correct
13 Correct 12 ms 11272 KB Output is correct
14 Correct 12 ms 11304 KB Output is correct
15 Correct 13 ms 11256 KB Output is correct
16 Correct 12 ms 11372 KB Output is correct
17 Correct 13 ms 10872 KB Output is correct
18 Execution timed out 1066 ms 26656 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11356 KB Output is correct
2 Correct 12 ms 11276 KB Output is correct
3 Correct 13 ms 10996 KB Output is correct
4 Correct 15 ms 10584 KB Output is correct
5 Correct 15 ms 10844 KB Output is correct
6 Correct 15 ms 10844 KB Output is correct
7 Execution timed out 1066 ms 26656 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 11260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 5 ms 11096 KB Output is correct
8 Correct 3 ms 9560 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9564 KB Output is correct
12 Correct 3 ms 9768 KB Output is correct
13 Correct 3 ms 9308 KB Output is correct
14 Correct 3 ms 9388 KB Output is correct
15 Correct 12 ms 11356 KB Output is correct
16 Correct 12 ms 11276 KB Output is correct
17 Correct 13 ms 10996 KB Output is correct
18 Correct 13 ms 11136 KB Output is correct
19 Correct 13 ms 10844 KB Output is correct
20 Correct 12 ms 11272 KB Output is correct
21 Correct 12 ms 11304 KB Output is correct
22 Correct 13 ms 11256 KB Output is correct
23 Correct 12 ms 11372 KB Output is correct
24 Correct 13 ms 10872 KB Output is correct
25 Correct 15 ms 10584 KB Output is correct
26 Correct 15 ms 10844 KB Output is correct
27 Correct 15 ms 10844 KB Output is correct
28 Correct 16 ms 10840 KB Output is correct
29 Correct 15 ms 10844 KB Output is correct
30 Correct 15 ms 10816 KB Output is correct
31 Correct 15 ms 10844 KB Output is correct
32 Correct 16 ms 11020 KB Output is correct
33 Correct 16 ms 10588 KB Output is correct
34 Correct 15 ms 10844 KB Output is correct
35 Execution timed out 1066 ms 26656 KB Time limit exceeded
36 Halted 0 ms 0 KB -