oj.uz

Submission #1000744

# Submission time Handle Problem Language Result Execution time Memory
1000744 2024-06-18T08:05:42 Z vuavisao September (APIO24_september) C++17
34 / 100
 1000 ms 28568 KB 
#include "september.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100'000 + 10;
const int INF = 1'000'000'000;
 
const uint8_t size_T = 2;
const int _1hrd = 100;
const int _1bil = 1000000000;
const array<int, size_T> MOD = {_1bil + 9, _1bil + 11};
const array<int, size_T> BASE = {_1hrd + 28, _1hrd + 31};
 
struct Hash {
	array<int, size_T> val = {0};
	Hash() {};
	Hash (int x) {
		for (uint8_t i = 0; i < size_T; ++ i)
			this->val[i] = x % MOD[i];
	}
 
	bool operator < (const Hash& other) const {
		for (uint8_t i = 0; i < size_T; ++ i)
			if (this->val[i] != other.val[i]) return this->val[i] < other.val[i];
		return false;
	}
 
	bool operator == (const Hash& other) const {
		for (uint8_t i = 0; i < size_T; ++ i)
			if (this->val[i] != other.val[i]) return false;
		return true;
	}
 
	Hash operator + (const int& x) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (1ll * this->val[i] * BASE[i] + x) % MOD[i];
		return res;
	}
 
	Hash operator + (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (this->val[i] + other.val[i]) % MOD[i];
		return res;
	}
 
	Hash operator - (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i) {
			res.val[i] = (this->val[i] - other.val[i]) % MOD[i];
			res.val[i] = (res.val[i] + MOD[i]) % MOD[i];
		}
		return res;
	}
 
	Hash operator * (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (1ll * this->val[i] * other.val[i]) % MOD[i];
		return res;
	}
 
	friend ostream& operator << (ostream& os, Hash& other) {
		os << "[ ";
		for (uint8_t i = 0; i < size_T; ++ i) {
			cout << other.val[i];
			if(i < size_T - 1) cout << ',';
			cout << ' ';
		}
		os << "]";
		return os;
	}
};

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 Line {
// 	bool check() {
// 		for (int v = 2; v <= n; ++ v) {
// 			if (parent[v] != v - 1) return false;
// 		}
// 		return true;
// 	}

// 	int calc() {
		
// 	}
// }
 
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 (OneLine::check()) {
	// 	return OneLine::calc();
	// }
	if (One::check()) {
		return One::solve();
	}
	// if (Line::check()) {
	// 	return Line::calc();
	// }
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Incorrect 2 ms 13916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 6 ms 13912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Incorrect 2 ms 13916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 988 ms 28456 KB Output is correct
5 Correct 958 ms 28568 KB Output is correct
6 Correct 986 ms 28244 KB Output is correct

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 3 ms 9820 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 3 ms 9820 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 988 ms 28456 KB Output is correct
19 Correct 958 ms 28568 KB Output is correct
20 Correct 986 ms 28244 KB Output is correct
21 Execution timed out 1012 ms 26024 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 6 ms 13912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Incorrect 2 ms 13916 KB Output isn't correct
9 Halted 0 ms 0 KB -