oj.uz

Submission #1000755

# Submission time Handle Problem Language Result Execution time Memory
1000755 2024-06-18T08:22:16 Z vuavisao September (APIO24_september) C++17
64 / 100
 1000 ms 31708 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;
	vector<int> tree = {};

	void resize(int n) { n_node = n; tree.resize(n + 10, 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;
		vector<Node> tree = {};
	
		void resize(int _n) { n_node = _n; tree.clear(); tree.resize((n_node << 2) + 10); };
		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 > r || L > R || l > R || L > r) return Node();
			if (L <= l && r <= R) return tree[node]; 
			int mid = (l + r) >> 1;
			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 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9816 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 4 ms 10076 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 4 ms 11096 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 4 ms 10328 KB Output is correct
12 Correct 3 ms 10076 KB Output is correct
13 Correct 4 ms 10076 KB Output is correct
14 Correct 4 ms 9852 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 4 ms 11100 KB Output is correct
17 Correct 4 ms 10076 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 4 ms 10076 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 14 ms 10932 KB Output is correct
5 Correct 14 ms 12124 KB Output is correct
6 Correct 14 ms 11044 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9816 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 4 ms 11096 KB Output is correct
16 Correct 4 ms 10076 KB Output is correct
17 Correct 3 ms 11100 KB Output is correct
18 Correct 4 ms 10328 KB Output is correct
19 Correct 3 ms 10076 KB Output is correct
20 Correct 4 ms 10076 KB Output is correct
21 Correct 4 ms 9852 KB Output is correct
22 Correct 3 ms 9820 KB Output is correct
23 Correct 4 ms 11100 KB Output is correct
24 Correct 4 ms 10076 KB Output is correct
25 Correct 14 ms 10932 KB Output is correct
26 Correct 14 ms 12124 KB Output is correct
27 Correct 14 ms 11044 KB Output is correct
28 Correct 14 ms 11020 KB Output is correct
29 Correct 14 ms 10844 KB Output is correct
30 Correct 14 ms 11912 KB Output is correct
31 Correct 15 ms 10844 KB Output is correct
32 Correct 14 ms 11908 KB Output is correct
33 Correct 15 ms 12084 KB Output is correct
34 Correct 14 ms 11868 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 4 ms 10076 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 913 ms 27508 KB Output is correct
5 Correct 897 ms 27704 KB Output is correct
6 Correct 920 ms 27700 KB Output is correct

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 4 ms 11096 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 4 ms 10328 KB Output is correct
12 Correct 3 ms 10076 KB Output is correct
13 Correct 4 ms 10076 KB Output is correct
14 Correct 4 ms 9852 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 4 ms 11100 KB Output is correct
17 Correct 4 ms 10076 KB Output is correct
18 Correct 913 ms 27508 KB Output is correct
19 Correct 897 ms 27704 KB Output is correct
20 Correct 920 ms 27700 KB Output is correct
21 Execution timed out 1047 ms 25468 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 4 ms 10076 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 14 ms 10932 KB Output is correct
5 Correct 14 ms 12124 KB Output is correct
6 Correct 14 ms 11044 KB Output is correct
7 Correct 913 ms 27508 KB Output is correct
8 Correct 897 ms 27704 KB Output is correct
9 Correct 920 ms 27700 KB Output is correct
10 Incorrect 834 ms 31708 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11100 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9816 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 4 ms 11096 KB Output is correct
16 Correct 4 ms 10076 KB Output is correct
17 Correct 3 ms 11100 KB Output is correct
18 Correct 4 ms 10328 KB Output is correct
19 Correct 3 ms 10076 KB Output is correct
20 Correct 4 ms 10076 KB Output is correct
21 Correct 4 ms 9852 KB Output is correct
22 Correct 3 ms 9820 KB Output is correct
23 Correct 4 ms 11100 KB Output is correct
24 Correct 4 ms 10076 KB Output is correct
25 Correct 14 ms 10932 KB Output is correct
26 Correct 14 ms 12124 KB Output is correct
27 Correct 14 ms 11044 KB Output is correct
28 Correct 14 ms 11020 KB Output is correct
29 Correct 14 ms 10844 KB Output is correct
30 Correct 14 ms 11912 KB Output is correct
31 Correct 15 ms 10844 KB Output is correct
32 Correct 14 ms 11908 KB Output is correct
33 Correct 15 ms 12084 KB Output is correct
34 Correct 14 ms 11868 KB Output is correct
35 Correct 913 ms 27508 KB Output is correct
36 Correct 897 ms 27704 KB Output is correct
37 Correct 920 ms 27700 KB Output is correct
38 Execution timed out 1047 ms 25468 KB Time limit exceeded
39 Halted 0 ms 0 KB -