oj.uz

Submission #1000677

# Submission time Handle Problem Language Result Execution time Memory
1000677 2024-06-18T07:05:49 Z vuavisao September (APIO24_september) C++17
0 / 100
 2 ms 2908 KB 
#include "september.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100'000 + 10;
 
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;
	}
};
 
int n, m;
int parent[N];
vector<int> g[N];
int perRem[10][N];
 
namespace One {
	bool check() {
		return m == 1;
	}
 
	const int INF = 1'000'000'000;
 
	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.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);
		}
	};
 
	bool visited[N];
	bool un_visited[N];
	SegTree st;
 
	void dfs(int u, bool save, vector<int>& roll_back) {
		if (visited[u]) return;
		if (save) {
			roll_back.push_back(u);
		}
		visited[u] = true;
		st.Update(u, 0);
		for (const auto& v : g[u]) {
			if (visited[v]) continue;
			dfs(v, save, roll_back);
		}
	}
 
	int dp[N];
 
	int calc() {
		st.resize(n);
		for (int i = 0; i <= n + 1; ++ i) dp[i] = -INF;
		for (int i = 0; i <= n + 1; ++ i) visited[i] = un_visited[i] = false;
		dp[0] = 0;
		for (int i = 0; i < n - 1; ++ i) {
			vector<int> roll_back;
			if (i >= 1) {
				int u = perRem[1][i];
				dfs(u, false, roll_back);
				st.Update(u, -1);
			}
			if (dp[i] < 0) continue;
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (visited[u]) continue;
				un_visited[u] = true;
			}
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (un_visited[u]) {
					dfs(u, true, roll_back);
				}
				st.Update(u, -1);
				if (st.Query(1, n).val < 0) {
					dp[j] = max(dp[j], dp[i] + 1);
				}
			}
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (!un_visited[u]) {
					st.Update(u, 0);
				}
				un_visited[u] = false;
			}
			for (const auto& u : roll_back) {
				visited[u] = false;
				st.Update(u, -INF);
			}
		}
		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);
		// 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';
		}
	}
 
	// if (OneLine::check()) {
	// 	return OneLine::calc();
	// }
	if (One::check()) {
		return One::calc();
	}
	// if (Line::check()) {
	// 	return Line::calc();
	// }
	return 0;
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 14.0

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

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 9.0

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

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

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

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

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